首页 > 代码库 > 【Leetcode】动态规划问题详解（持续更新）
【Leetcode】动态规划问题详解（持续更新）
1、动态规划算法步骤（Dynamic Programming）
动态规划算法一般用来求解最优化问题，当问题有很多可行解，而题目要求寻找这些解当中的“最大值”/“最小值”时，通常可以采用DP。
动态规划算法与分治法相似，都是通过组合子问题的解来求解原问题。所不同的是，动态规划应用于子问题重叠的情况，在递归求解子问题的时候，一些子子问题可能是相同的，这种情况下，分治法会反复地计算同样的子问题，而动态规划对于相同的子问题只计算一次。
动态规划算法的设计步骤：
1、刻画最优解的结构特征（寻找最优子结构）
2、递归地定义最优解的值（确定递归公式）
3、计算最优解的值（有两种方法：带备忘录自顶向下法、自底向上法）
4、利用计算出的信息构造一个最优解（通常是将具体的最优解输出）
2、leetcode上适合用DP求解的问题
| 题目 | OJ地址 | 目录 |
Triangle | https://oj.leetcode.com/problems/triangle/ | 3.1 |
| Maximum Subarray | https://oj.leetcode.com/problems/maximum-subarray/ | 3.2 |
Palindrome Partitioning II | https://oj.leetcode.com/problems/palindrome-partitioning-ii/ | 3.3 |
| Minimum Path Sum | https://oj.leetcode.com/problems/minimum-path-sum/ | 3.4 |
| Maximal Rectangle | https://oj.leetcode.com/problems/maximal-rectangle/ | 3.5 |
Interleaving String | https://oj.leetcode.com/problems/interleaving-string/ | 3.6 |
| Edit Distance | https://oj.leetcode.com/problems/edit-distance/ | 3.7 |
Decode Ways | https://oj.leetcode.com/problems/decode-ways/ | 3.8 |
Best Time to Buy and Sell StocI&II&III | https://oj.leetcode.com/problems/best-time-to-buy-and-sell-stock/ | 3.9 |
Scramble String | https://oj.leetcode.com/problems/scramble-string/ | 3.10 |
Distinct Subsequences | https://oj.leetcode.com/problems/distinct-subsequences/ | 3.11 |
| Word Break I&II | https://oj.leetcode.com/problems/word-break/ | 3.12 |
3、leetcode相关题目
3.1 Triangle
3.1.1 题目
Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
Note:
Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
3.1.2 分析
题目大意：从最顶端往下走，寻找和最小的路径。
显然，从最顶端往下走有很多条路径可以走，但是每一条路径的sum不一样，题目要求sum最小，属于最优化问题，考虑动态规划。
如果用暴力破解，复杂度如何？观察题目所给的三角形，对于每个“节点”，往下都有两条路可以走，比如2可以往3、4走，3可以往6、5走，4可以往5、7走.......类似于二叉树，如果有n行，则一共有路径2^n条，时间复杂度O(2^n)。
用动态规划的话，时间复杂度可以降到O(n^2)。下面按照动态规划的步骤来分析这道题：
#1 最优解的结构特征
第一个步骤要搞清楚怎么将问题分解为更小的子问题。上面已经提到，“2”往下走都有两条路可以选择，分别是“3”、“4”，因此从2出发的最优路径，其实就是从“3”出发的最优路径、从“4”出发的最优路径 这两者中sum最小的一条。
#2 确定递归求解公式
用f(i,j)表示从点(i,j)出发的最优路径的sum，根据上面分析，易得递归公式 ：f(i,j)=min{f(i+1,j),f(i+1,j+1)}+Val(i,j)
Val(i,j)表示点(i,j)的值。
#3 根据递归公式求解
分别用“自底向上”、“带备忘录的自顶向下”两种方法，见3.1.3代码
3.1.3 参考代码
自底向上法，注意到f(0,0)取决于f(1,0)、f(1,1); f(1,0)又取决于f(2,0)、f(2,1)......所以从最底层开始计算是比较自然的做法，而最底层的最短路径和就是节点本身的值，因此实际上是从倒数第二层开始计算。
int minimumTotal(vector<vector<int> > &triangle) {
int row=triangle.size(); //行,第row行的元素有row个
vector<vector<int> > f(triangle);
//用f[m][n]记录从triangle[m][n]出发到叶子节点的最短路径和。也可以直接用triangle代替f，但会改变triangle
for(int x=row-2;x>=0;x--)
for(int y=0;y<=x;y++)
f[x][y]=min(f[x+1][y],f[x+1][y+1])+triangle[x][y];
return f[0][0];
}带备忘录的自顶向下法
class Solution {
public:
int minimumTotal(vector<vector<int> > &triangle) {
int row=triangle.size(); //行
vector<vector<int> > f(triangle); //f[m][n]表示从triangle[m][n]出发到叶子节点的最短路径和
for(int m=0;m<row-1;m++)
for(int n=0;n<=m;n++)
f[m][n]=INT_MAX; //与自底向上的方法不同，备忘录法必须将其初始化为标识值，以便“查找备忘录”
f[row-1]=triangle[row-1]; //最后一行保持原值
return dp(0,0,triangle,f); //从根出发
}
private:
int dp(int x,int y,vector<vector<int> > &triangle,vector<vector<int> > &f){
if(f[x][y]!=INT_MAX) return f[x][y]; //查找备忘录，如果已经计算过，直接返回，避免重复计算
f[x][y]=min(dp(x+1,y,triangle,f),dp(x+1,y+1,triangle,f))+triangle[x][y];
return f[x][y];
}
};【Leetcode】动态规划问题详解（持续更新）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。