详解动态规划法(包含完整可用的代码实例)

由于STL库更方便，本文用的是vector，没有用数组。

文中程序可以直接运行，可当做模板进行修改。

目录

一、动态规划算法思想

二、动态规划处理一维问题(以走台阶为例)

三、动态规划处理二维问题(以从矩阵左上角走到右下角最短路径问题为例)

四、动态规划求子序列(以求最长严格递增子序列长度为例)

五、最长公共子序列的长度

六、输出最长公共子序列

  动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。

分治法核心思想： 从上往下分析问题，大问题可以分解为子问题，子问题中还有更小的子问题

动态规划法思想：自底向上，推导递推公式，避免重复计算，降低计算量

问题描述：有10级台阶，一个人每次上一级或者两级，问有多少种走完10级台阶的方法。

解法：

因为问的是一共有多少种走法，则走到第n个台阶时的总走法应该是在第n-1级台阶时的总走法(再走一步一级跨越)加上在第n-2级台阶时的总走法(再走一步二级跨越)，这里从上一步到第n台阶为什么不加1呢？因为从n-1台阶或者n-2台阶到n台阶就是一种走法。

1.设数组dp：每个位置存的值代表该台阶位置的总走法。(注意数组是从0开始的，即dp[0]代表台阶1)

2.分析边界条件：因为每次可以上一级或者两级，所以边界分析时需要考虑到两级台阶。当台阶数为1时走法为1（即走一级即毕），台阶数为2时走法为2（走两次一级和走一次二级）。

即：dp[0] = 1;    dp[1] = 2;

3.分析递归关系：对于任一台阶都可以分为通过两级或者一级到达。

即：dp[i] = dp[i - 1] + dp[i - 2];

4.遍历台阶：遍历台阶，数组的每个数值代表的是到该位置的总的走法，则数组最后一个位置的值就是总的走法。