进阶
进阶
是否能够使用动态规划的核心
是否存在一种状态表示方法
可以使得状态之间的依赖关系可以被拓扑排序（DAG）
推论：动态规划处理的状态要有方向性（才不会有循环依赖）
看不懂没关系，之后做题慢慢带着这个推论去体会
坐标
停在原地的方案数
状态：dp[i][j]表示走了i次以后，走到坐标j的路径数
方法：把所有可能会影响到结果的信息都往状态数组里丢
时间复杂度：通用计算公式O状态总数计算每个状态的时间)
子序列
子序列 Subsequence
题目一般会让你找最长子序列或者子序列的个数之类的子序列属于一维坐标型DP
dp表示以下标ⅰ作为结尾的子序列的最优值/方案数/何行性
问：n个数的数组有多少个subsequences?(数量级) O2n
不同的子序列
给定一个小写字母组成的字符串S，问S中不同的非空子序列的个数
状态：f[i]表示以下标 i 字符结尾的不同子序列有多少个
转移：f[i]=sum{f[j]|a[i] not in f[j+1,i-1]}
边界：f[i]=1, a[i]是第一次出现
和
题目中有若平个数之和>或者<的限制条件
一般使用背包型DP
盈利计划
有n个项目，G个人
每个项目需要用group[i]个人，可以获得profit[i]的利润
一个人不能同时参与多个项目
求利润最少为P的方案总数
求方案数、有和信息
和=>背包DP
有哪些信息应该放到状态中？
多选：项目数、人数、利润
状态：f[i][j][k]表示前i个项目，用了j个人，获得至少k的收益的方案总数
转移：f[i][j][k]=f[i-1][j][k]+f[i-1][j-g[i-1][k-p[i-1]]]
边界：f[0][0][0]=1
答案：
注：group[i-1]是第i个项目需要用的人数（第i个数index-=i-1)
j>=group[i-]时才可以选择做第i个项目
如果k-profit[i-1]<0则让这个维度的数值=0
可以滚i
老鼠游戏
坐标型+状态型（需要知道来这里之前的一步的状态）
状态：f[i][j]表示从0跳奇/偶数步(j)到坐标i位置的方案数
转移：f[i][j]=0|arr[i]==1, sum{f[i-k][1-j]}
边界：f[0][0]=1
优化：可以滚动i，开5个大小，因为最多需要从4步前拿状态
全1正方形
求一个01矩阵中，全为1的正方形个数
坐标型2维
浮点数组合和
给 n 个 >= 0 的 float, 每个数可以向上或者向下取整，调整目标是所有数之和为target，代价是每个数调整后差值绝对值，问最小调整代价所对应的具体方案
分组01背包，每组是一个数，组内两个方案向上或向下
prev[i][j]存具体的选择，倒推法
状态：f[i][j]表示前i个数，凑出j的和，最小的调整代价是多少
转移：
边界：
合并石头的最低成本
一条直线上有 N 堆石头，每次可以合并连续的 K 堆石头，代价是 K 堆石头之和，问最终需要合并成一堆的最小代价之和
区间dp
状态：f[i][j][k]表示i到j这一段合并为k堆石子的最小代价
转移：f[i][j][k]=min{f[i][x][k-1]+f[x][j][1]}+sum(i,j)
答案：f[0][n-1][1]
跳跃游戏
状态：f[i]表示前i个位置最大可以跳到哪里
转移：f[i]=max{f[i-1],nums[i-1]+i-1|f[i-1]>i-1}
边界：f[0]=0
答案：f[n]>=n-1
滚i，开2或者一个变量即可
贪心法只能解决这两题，动规n2但是很有通用性
状态：f[i]表示可以跳到坐标i
转移：f[i]=or{j+nums[j]>=i}
边界：f[0]=true
答案：f[n-1]
跳跃游戏II
问一开始站在 index=0 一直向右跳最少跳几次跳到 index = n-1
状态：f[i]表示前i个位置最大可以跳到哪里
转移：f[i]=max{f[i-1],nums[i-1]+i-1|f[i-1]>i-1}
边界：f[0]=0
答案：
状态：f[i]表示跳到坐标i最小步数
转移：f[i]=min{f[j]|f[j]+nums[j]>=i}+1
边界：f[0]=0
答案：f[n-1]
找到最大的全1正方形
找到最大的对角线全1其他全0的正方形
最大矩形的不行，这种需要单调栈