动态规划详解
定义
动态规划（Dynamic programming）是一种在数学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。
若要解一个给定问题，我们需要解其不同部分（即子问题），再合并子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量： 一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表（空间换时间）。 这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。
性质
最优子结构性质
如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。
子问题重叠性质
子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的效率。
无后效性：
即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。
步骤
- 划分：按照问题的特征，把问题分为若干
阶段，就是写出循环过程或递归关系。注意：划分后的阶段一定是有序的或者可排序的 - 确定状态和状态变量：定义结果数组 dp，
保存过程解。 将问题发展到各个阶段时所处的各种不同的客观情况表现出来。状态的选择要满足无后续性 - 确定决策并写出
状态转移方程：状态转移就是根据上一阶段的决策和状态来导出本阶段的状态。根据相邻两个阶段状态之间的联系来确定决策方法和状态转移方程 - 边界条件：状态转移方程是一个递推式，因此需要找到递推
终止的条件
即：
【初始状态】→【决策 1】→【决策 2】→…→【决策 n】→【结束状态】
注意：
- 问题阶段
- 每个阶段的状态
- 相邻两个阶段之间的递归关系
动态规划与递归
递归：自顶向下
从上向下延伸，从一个规模较大的原问题比如说 f(20)，向下逐渐分解规模，直到 f(1) 和 f(2) 触底，然后逐层返回答案，这就叫「自顶向下」
1
2
3
4
5
6
7
8
9
// 递归法计算斐波那契数列
int Fibonacci(size_t n)
{
if (n == 1 || n == 2)
{
return n;
}
return Fibonacci1(n - 1) + Fibonacci1(n - 2);
}
也就是从上向下看，遇到问题，发现解决不了，必须解决子问题，就先解决子问题，最后逐步返回
缺点是重复解决子问题，比如Fibonacci1(n - 1)实际包含了子问题Fibonacci1(n - 2)和Fibonacci1(n - 3)，和Fibonacci1(n)的子问题Fibonacci1(n - 2)重复了。根因是使用了栈空间保存子问题的解导致问题之间不能共享子问题的解
另一个缺点的栈的深度不可控
动态规划：自底向上
问题规模最小的 f(1) 和 f(2) 开始往上推，直到推到我们想要的答案 f(20)
1
2
3
4
5
6
7
8
9
// 动态规划法计算斐波那契数列
int fib(int N)
{
vector<int> dp(N + 1, 0);
dp[1] = dp[2] = 1;
for (int i = 3; i <= N; i++)
dp[i] = dp[i - 1] + dp[i - 2];
return dp[N];
}
dp[i] = dp[i - 1] + dp[i - 2];称为状态转移方程，表示如果利用子问题的解得到当前问题的最优解，当前问题为 dp[i] 的值，子问题的解为 dp[i - 1] 和 dp[i - 2]，这里只是很简单的相加就是最优解，复杂的比如求两者间的最大值作为最优解（最优策略）。
缺点是需要一个 dp 数组保存已经解决的子问题，优点是问题之间可以共享解，无需重复解子问题。
实例
题目
每行的各个值只能和正下或右下的值相连，求值总和最大的路径的总和值
1
2
3
4
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
递归解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution
{
public:
int getMax()
{
int MAX = 5;
int[][] D = new int[MAX][MAX]; // 存储问题中的数字三角形
int n = MAX; // n表示总行数
int i = 0; // i表示当前行数
int j = 0; // j表示行偏移
int maxSum = getMaxSum(D, n, i, j);
return maxSum;
}
int getMaxSum(int[][] D, int n, int i, int j)
{
if (i == n) // 结束条件
{
return D[i][j];
}
// 子问题1：正下方的最优路径值总和
int x = getMaxSum(D, n, i + 1, j);
// 子问题2: 右下方的最优路径值总和
int y = getMaxSum(D, n, i + 1, j + 1);
// 当前问题：当前最优路径值总和
return Math.max(x, y) + D[i][j];
}
}
重复计算
下面为全部计算完成后每个解重复计算的次数
1
2
3
4
5
7
3 8
8 1(2) 0
2 7(3) 4(3) 4
4 5(4) 2(6) 6(4) 5
动态规划解法
1
2
3
4
5
6
for(int i = n-2; i >= 0; i--) {
for(int j = 0; j <= i; j++) {
// 状态转移方程，当前最优解为下方两个中最大的值和自身值之和
maxSum[i][j] = Math.max(maxSum[i+1][j], maxSum[i+1][j+1]) + D[i][j];
}
}
利用 maxSum 保存已计算的解结果，已经被舍弃的分支不会再被重复计算。
练习 1
问题：爬楼梯
楼梯有 n 阶，一次能爬 1 阶或 2 阶，爬到顶一共有几种可能的走法
分析
定义保存状态变量：dp[x]用于保存当前状态(剩余 x 阶未走)下剩余走法可能性
状态转移方程：dp[i] = dp[i-1] + dp[i-2];
递归解法
1
2
3
4
5
6
7
8
9
10
11
// n：剩余阶数
int possibleNum(int n){
if (n == 1){
return 1;
}
if (n == 2){
return 2;
}
return possibleNum(n-1) + possibleNum(n-2)
}
动态规划解法
1
2
3
4
5
6
7
dp[1] = 1;
dp[2] = 2;
for(int i=3;i<=n;i++)
{
dp[i] = dp[i-1] + dp[i-2];
}
练习 2
问题：走格子
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
分析
定义保存状态变量：dp[x][y]用于保存当前状态(离左边格子 x，离上边格子 y)下走法可能性
状态转移方程：dp[i][j] = dp[i-1][j] + dp[i][j-1];
表示该点上面一个点和左边一个点可能的走法，加起来就是到该点可能的走法
动态规划解法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
dp[0][0] = 0;
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(i==0 || j==0)
{
dp[i][j] = 1;
}
else
{
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
}
扩展：权值
为每个格子附上权值，求权值最小的走法的总权值？
状态转移方程：dp[i][j] = MIN(dp[i-1][j],dp[i][j-1]);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const cost[m][n]; //权值
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(i==0 && j==0)
{
dp[i][j] = cost[i][j];
}
else if(i==0)
{
dp[i][j] = dp[i][j-1] + cost[i][j];
}
else if(j==0)
{
dp[i][j] = dp[i-1][j] + cost[i][j];
}
else
{
dp[i][j] = MIN(dp[i-1][j],dp[i][j-1]) + cost[i][j];
}
}
}