一、动态规划最精辟的总结
首先， 动态既不是什么动态，也不是什么规划，存粹就是对递归的优化；
其次，动态规划依赖于两个基本情况：边界条件和递推关系，边界条件就是最简单的情况，所谓递推关系就是如果你已经知道这么多，再多给你一个，你怎么得到。
二、动态规划的经典模型
1、线性模型
2、区间模型
3、背包模型
4、状态压缩模型
5、树状模型
https://blog.csdn.net/y389224734/article/details/81269245?utm_medium=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-1.control&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2%7Edefault%7EBlogCommendFromMachineLearnPai2%7Edefault-1.control
关于搜索过程是否需要保存所有状态，我觉得不在于算法（DFS或BFS），而在于实现方式（递归或迭代）。
在多叉树遍历中，递归和迭代的计算过程并不完全一样。递归的形式，在某个“节点”中，递归调用前和后都可以执行自定义逻辑；而用显式栈迭代的形式，在某个“节点”中只能先做自定义逻辑，再将所有孩子（子状态）依次入栈，而做不了“在递归调用后执行逻辑”这个过程，所以每个节点都需要保存当时走到这儿时的状态，可以用多个平行栈，或者用自定义类的多个属性，就像您下边回复里定义的Ceil类，这其实也是模拟了递归时的系统栈帧，栈帧中保存的方法入参和显式栈中保存的多个变量值或类的多个属性值就表征了此时的局面。
而BFS一般无法用递归的形式，在用队列迭代的过程中，每个结点也是一旦走过就永远错过了，所以也需要自己保留自己的状态。
顺便再说下我对动规的理解，动规中常提的“状态”实际就是回溯中的“状态”去掉路径和选择列表。回溯中随着不断的决策也是会到达一个个子局面，因为回溯是穷举，所以他要记录我是怎么到达这个子局面的；而动规是：我们先分析下可能会到达哪些子局面，然后先把子局面的解求出来，再根据当前状态的选择列表，将每个可做出的选择会到达的子局面的解通过某种关系组合，这个关系就是状态转移方程，这个组合形式就叫最优子结构
https://leetcode.com/problems/maximal-square/ 这个题就是对这个动归最好的理解；
三 关于怎么定义状态
所谓「状态」，就是指当前的任务进行到哪个阶段了，可以用变量来表示，怎么定义状态有的时候需要一定技巧，这道题不难。这里分别定义两个水壶为 A 和 B，定义有序整数对 (a, b) 表示当前 A 和 B 两个水壶的水量，它就是一个状态。
四 动态规划我自己的定义
最优子结构就是能产生链式反应的结构，比如跳台阶，然后可以着手暴力解，但这个暴力解不是通过递归来实现的，暴力解之后你就要看是否右重叠子结构，然后就可以着手优化了；
参考了：https://github.com/labuladong/fucking-algorithm/blob/master/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%E7%B3%BB%E5%88%97/%E6%9C%80%E4%BC%98%E5%AD%90%E7%BB%93%E6%9E%84.md
五 动态规划的分类
1）暴力思路(回溯) dfs的递归本身就是逆推的 就是所谓的自顶向下，然后就归
174. Dungeon Game
回溯公式： dfs(0, 0, rowLen, colLen, dungeon)+1;
退出条件：达到最后一个且最后一个的值>=0
继续递归： int rightMin=dfs(rowIndex, colIndex+1, rowSize, colSize, dungeon);
结果： int needMin = Math.min(rightMin, downMin)+dungeon[rowIndex][colIndex];
22. Generate Parentheses
倒序
sb.append('('); //左边配置一个(，必然左边要去回溯；
dfs(res, left-1, right, sb); //sb用来创建字符串 所以要用StringBuilder
sb.deleteCharAt(sb.length-1);
45. Jump Game II
far_max = Math.max(far_max, i+nums[i]); //i+nums[i]是这题的关键
55. Jump Game
far_max = Math.max(far_max, i+nums[i]);
return fax_max>=n-1;
53. Maximum Subarray
sum = Math.max(nums[i], sum+nums[i]); //贪心
77. Combinations
res.add(new LinkedList<Integer>(track));
关键：track.add(i); backtrack(track, i+1, n, k); track.removeLast();
152. Maximum Product Subarray
这题跟53题是一样的，多出来的一点是：if(nums[i]<0) 即要对调；我觉得刷题最耗时间的是理解，找到最容易理解的方式那就是最节约时间的方式，也是最高效的，因为算法都是套路；
minValue = Math.min(nums[i], minValue*nums[i]);
2）记忆化搜索
174. Dungeon Game
int[][] memo = new int[m][n];
Math.min(dp(i, j+1, dungeon), dp(i+1, j, dungeon))+dungeon[rowIndex][colIndex];
10. Regular Expression Matching
res = isMatch(s, p.substring(2)) || isMatch(s.substring(1),p);
res = isMatch(s.substring(1),p.substring(1));
3）dp数组 - 递推，自底向上
174. Dungeon Game
//倒序：从（i，j）出发，到达终点需要最少的血量
Math.min(dp[i][j+1], dp[i+1][j])-dungeon[rowIndex][colIndex];
44. Wildcard Matching
if(s.charAt(i-1)==p.charAt(j-1) || p.charAt(j-1)=='?') //如果第1个字母相等 或 第一个字母是?
dp[i][j] = dp[i-1][j-1];
if(p.charAt(j-1)=='*') //只要pattern的第一个字母是* 即可以去掉i的第一个字母，也可以去掉j的第一个字母
dp[i][j] = dp[i-1][j]||dp[i][j-1]; //往上、往下都没问题
62. Unique Paths
到dp[m-1][n-1]这个坐标有多少种走法？
dp[i][j] = dp[i][j+1]+dp[i+1][j];
63. Unique Paths II
到dp[m-1][n-1]这个坐标有多少种走法？虽然有障碍
if(obstacleGrid[i][j]==1) dp[i][j] = 0; //此路不通
else if(i==0 && j==0) dp[i][j] = 1;
else if(i==0 && j>0) dp[i][j] = dp[i][j-1];
else if(i>0 && j==0) dp[i][j] = dp[i-1][j];
else dp[i][j] = dp[i-1][j]+dp[i][j-1];
64. Minimum Path Sum
if(i==0 && j==0) dp[i][j] = grid[i][j]; //0 0位置实际上是第一个位置
else if(i>0 && j==0) dp[i][j] = grid[i][j]+dp[i-1][j];
else if(i==0 && j>0) dp[i][j] = grid[i][j]+dp[i][j-1];
else dp[i][j] = grid[i][j]+Math.min(dp[i][j-1],dp[i-1][j]); //这是关键
70. Climbing Stairs
dp的定义：也是有多少种跳法；
dp[1]=1;
dp[2]=2;
dp[i]=dp[i-1]+dp[i-2];
72. Edit Distance
dp的定义：dp[m][n]是指需要多少步；
dp[i][j] = dp[i-1][j-1];
dp[i][j] = getMin(dp[i][j-1]+1, dp[i-1][j]+1, dp[i-1][j-1]+1);
85. Maximal Rectangle
dp[m][n] 应该标记的是高度，而count则是宽度；
关键的转移方程是：
if(matrix[r][c]=='1') dp[r][c]=dp[r-1][c]+1; //取决于下一排的情况
//n是宽
for(int k=c+1; kdp[r][c] 则count++
for(int k=c-1; k>=0; k--) if(dp[r][k] < dp[r][c]) break; count++;
最终的结果就是：Math.max(res, count*dp[r][c]);
91. Decode Ways
dp[]的定义：dp[n]是最终的结果；
dp[0]=1 //0个字符有1个拆解方法 //由于题目存在前导零，而前导零属于无效 item
if(s.charAt(i-1)!='0') dp[i] += dp[i-1]; //dp[i] = dp[i]+dp[i-1];
if(i>1 && s.charAt(i-2)!='0' && (s.charAt(i-2)-'0')*10+(s.charAt(i-1)-'0')<=26) dp[i] += dp[i-2]; //dp[i] = dp[i]+dp[i-2];
96. Unique Binary Search Trees
dp[i] += dp[j-1]*dp[i-j];
115. Distinct Subsequences
i最后一个字母不参与: dp[i][j] = dp[i-1][j]; //不是+=
最后一个字母参与：dp[i][j] += dp[i-1][j-1];
120. Triangle
n+1 //因为右i+1, j+1, 所以还是从0到n
//从底到顶，从左到右
dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1])+triangle.get(i).get(j);
return dp[0][0];
121. Best Time to Buy and Sell Stock
122. Best Time to Buy and Sell Stock II
123. Best Time to Buy and Sell Stock III
188. Best Time to Buy and Sell Stock IV
//不能同一天买卖
buy = Math.max(buy, -prices[i]); //-prices[i]就是负值，以昨天的卖为基准值 昨天有的
sell = Math.max(sell, buy+prices[i]);
//可以当天买卖
buy[i] = Math.max(buy[i-1], sell[i-1]-prices[i]); //与前一天比，昨天卖sell[i-1]，今天买-prices[i]
sell[i] = Math.max(sell[i-1], buy[i-1]+prices[i]);
//只有两次交易
buy1 = Math.max(buy1, -prices[i]);
sell1 = Math.max(sell1, buy1+prices[i]);
buy2 = Math.max(buy2, sell1-prices[i]); //上次卖
sell2 = Math.max(sell2, buy2+prices[i]);
//可以有K次交易
sell[i] = Math.max(sell[i], buy[i]+p);
buy[i] = Math.max(buy[i], sell[i-1]-p);
buy[j] = Math.max(buy[j],sell[j-1]-prices[i]); //前一天卖的
sell[j] = Math.max(sell[j],buy[j]+prices[i]);
139. Word Break
关键是从j到i的判断，然后就是HashSet是关键点；
if (dp[j]&&wordDicSet.contains(substring(j, i))) dp[i]=true; //dp[j]是一个小的范围，动态规划就是由小及大；
152. Maximum Product Subarray
这个是相乘积，这个怎么由小及大呢？
dp[i] = Math.max(dp[i]*dp[i-1]);
