动态规划总结

2019-11-19  本文已影响0人  GeorgeDon
动态规划

通过子问题递推求解最优的方法, 动态规划常常适用于有重叠子问题和最优子结构性质的问题 。

解题思路

动态的规划的关键是在于如下几点

练习开始时可以通过递归加缓存的方式求解动态规划,积累到一定经验之后最好是通过确定状态转移方程来求解这类问题

一般解题模板
int[][] dp=new int[m][n]
dp[0][0]=1
for(int i=0;i<m;i++){
 for(int j=0;j<M;j++){
 dp[i][j]=f(dp[i-1][j],dp[i][j-1])+xxx
 }
} 
return dp[m-1][n-1]
常见类型
1.线性序列dp

最简单的线性的dp问题,这类问题的状态方程直接通过递推就能得到,有的时候需要通过添加状态完(某个节点的状态有几种)

https://leetcode-cn.com/problems/unique-paths/

https://leetcode-cn.com/problems/unique-paths-ii/

https://leetcode-cn.com/problems/climbing-stairs/

2.区间dp

区间dp就是在区间上进行动态规划,求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。

https://leetcode-cn.com/problems/longest-palindromic-substring/ (最长回文子串,有很多解法,动态规划是比较容易理解的)

for(int len = 1;len<=n;len++){//枚举长度
   for(int j = 1;j+len<=n+1;j++){//枚举起点,ends<=n
   int ends = j+len - 1;
   for(int i = j;i<ends;i++){//枚举分割点,更新小区间最优解
   dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+something);
   }
 }
3.树形dp

树形dp的数据结构有一个特点,那就是数据能够组织成一颗树,可以遍历树进行求解,遍历的方向有两个

 public int f(TreeNode root) {
     int[] res = dfs(root);
     return Math.max(res[0],res[1]);
     }
     //res[0]为不包括根节点的最大值,res[1]为包括根节点的最大值
     private int[] dfs(TreeNode root){
     int[] res = new int[2];
     if(root == null)
     return res;
     int[] left = dfs(root.left);
     int[] right = dfs(root.right); 
     res[0] = Math.max(left[0],left[1])+Math.max(right[0],right[1]);
     res[1] = left[0] + right[0] + root.val;
     return res;
     }

https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

4.数位dp

https://leetcode-cn.com/problems/number-of-digit-one/

5.期望dp

https://leetcode-cn.com/problems/maximum-profit-in-job-scheduling/submissions/
由于数据是离散的,需要对数据先排序,然后做处理

参考

[动态规划常见的类型] https://blog.csdn.net/fjsd155/article/details/88833701

[动态规划] https://leetcode-cn.com/tag/dynamic-programming/

[区间dp入门] https://blog.csdn.net/qq_40772692/article/details/80183248

上一篇 下一篇

猜你喜欢

热点阅读