动态规划总结

动态规划

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

解题思路

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

• 确定状态 （dp[i],dp[i] [j]）

• 确定状态转移方程 dp[i] = f(dp[i-1]) ,前序已获得的状态不会影响后面的状态

• 确定边界值

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

一般解题模板

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的数据结构有一个特点，那就是数据能够组织成一颗树，可以遍历树进行求解，遍历的方向有两个

• 叶->根

• 根->叶：一般都是这个顺序，可以通过dfs后续遍历求解，这种情况一般父节点的状态都是通过几个子节点的状态组合转移

  https://leetcode-cn.com/problems/house-robber-iii/

 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