综合型
综合型
综合型动态规划
需要辅助数据结构算法（字母树，哈希表，二分查找）的动态规划
万变不离其宗
Minimum Adjustment Cost
最后一步：将A改成B,A[n-1]改成X,这一步代价是A[n-1]-X
需要确保X-B[n-2]<=Target
前面n-1个元素A[0.n-2]改成B[0.n-2],需要知道最小代价，并确保B[0.n-2]中任意两个相邻的元素的差不超过Target子问题
但是有一个问题，改A[n-1]时不知道Bn-2]是多少
- 只有知道了B[n-2],才能确定A[n-1]能改成B[n-2]-Target<=X<=B[n-2]+Target
不知道是多少就记录下来：序列加状态
状态：f[i][j]将A中前i个元素修改成B的最小代价，确保前i个改好的元素中任意两个相邻的元素的差不超过Target，并且A[i-1]改成j
转移：f[i][j]=min_{j-t<=k<=j+t}{f[i-1][k]}+|j-A[i-1]|
边界：f[1][j]=|j-a[0|
K Sum
给定数组A，包含n个互不相等的正整数，K个数和是t
背包，带物品个数限制
状态：f[i][k][s]表示前i个数中选出k个，使他们的和是s的方案数
转移：f[i][k][s]=f[i-1][k][s]+f[i-1][k-1][s-a[i-1]|s>=a[i-1]
边界：f[0][0][0]=1,f[0][0][s]=0
LIS
要是求优化
最后变成那个卡牌了
K Edit Distance
trie 树上dp（状态转移的路径在树上）
dp只依赖于之前的一条递归路径，所以可以无需额外怎么穿一个大状态的f数组，f数组跟着dfs带着跑，放在一个状态里
写起来思路和二叉树上打家劫舍比较像
frog jump
坐标+状态型DP
状态：f[i][j]表示是否能最后一跳j到a[i]
转移：f[i][j]=f[k][j-1] || f[k][j] || f[k][j+1] | a[k]=a[i]-j
设上一块石头是ak=ai-j,可以通过一个哈希表(ak→k)快速找到k
边界：f[1][1]=true | a[1]-a[0]=1