动态规划关键点:
-
1.找到最优子结构
-
2.储存中间状态：
-
3.递推公式（美其名曰：状态转移方程或者 DP 方程）
动态规划 和 递归或者分治 没有根本上的区别（关键看有无最优的子结构）
共性：找到重复子问题差异性：最优子结构、中途可以淘汰次优解关键点
动态规划代码模版
// 状态定义
dp = new int [m+1][n+1];
// 初始状态
dp[0][0] = x;
dp[0][1] = y;
...
// DP状态推导
for i = 0; i <= n; ++i {
for j = 0; j <= m; ++j {
...
dp[i][j] = min{dp[i-1][j], dp[i][j-1], etc};
}
}
return dp[m][n]; // 最优解