坐标型
坐标型
状态：f[i]表示以a[i]为结尾的子序列的某种性质
边界：f[0]就是以a[0]为结尾的子序列的性质（没法从前面推导）
本质上是找一个以i结尾的路径（子序列）
给定一个序列或网格，需要找到序列中某个/些子序列或网格中的某条路径的性质
坐标型动态规划的初始条件f[0]就是指以a[0]为结尾的子序列的性质
状态i表示以a为结尾的满足条件的子序列的性质
f[i][j]中的下标，表示以格子(i,j)为结尾的满足条件的路径的性质
- 最大值/最小值
- 个数
- 是否存在
一维型
fibonacci 数列
状态：f[i]表示第i个fib数列的值（也是一个小序列自己及前面两个得到）
转移：f[i]=f[i-1]+f[i-2]
边界：f[0]=0,f[1]=1
Jump Game 跳跃游戏
从0是否可以跳到n-1
状态：f[i]表示可以跳到坐标i
转移：f[i]=or{f[j]|j+nums[j]>=i}
边界：f[0]=true
答案：f[n-1]
Jump Game II 跳跃游戏II
问一开始站在 index=0 一直向右跳最少跳几次跳到 index = n-1
状态：f[i]表示跳到坐标i最小步数
转移：f[i]=min{f[j]|j+nums[j]>=i}+1
边界：f[0]=0
答案：f[n-1]
打家劫舍
如果用坐标型，这样写，边界不好搞有问题，但是如果用滚动数组还行
状态：f[i]表示抢i的最大值
转移：f[i]=a[i] + max{f[i-2], f[i-3]}
边界：f[0]=a[0],f[1]=a[1],f[2]=a[0]+a[2]
答案：max{f[n-1],f[n-2]}
不然可以多加边界判断
Bomb Enemy
暴力：Omnm
四周方向各dp一次，就是朝各个方向求炸的个数，然后结果就是遍历一遍二维数组和最大的，Omn
约束
老鼠跳跃 Rat Jump (LintCode 1861)
给定一个长n数组A，一个老鼠可以从A[0]开始跳，第奇数次跳可以跳1,2,4个单位，第偶数次跳可以跳1,3,4个单位。A[i]或者是0或者1，是1的时候表示该位置有胶水，一旦跳到有胶水的地方，就不能继续跳。问它有多少方式可以跳到A[n-1]或者更右边的位置。A[n-1]有胶水没关系。答案对10^9 +7取模。
坐标型+状态型（需要知道来这里之前的一步的状态）
状态：f[i][j]表示从0跳奇/偶数步到坐标i位置的方案数
转移：f[i][j]=0|arr[i]==1, sum{f[i-k][1-j]}|k in {1,2,4}
边界：f[0][0]=1
优化：可以滚动i，开5个大小，因为最多需要从4步前拿状态
Frog Jump
有一条小河上有N个石头，位置依次在a0<a1<...<an-1
• 有一只青蛙在第一个石头上
• 青蛙一开始可以向右跳距离为1
• 它必须一直向右跳，并且落在石头上如果上次跳的距离是L，这次跳的距离可以是L-1, L或者L+1
问能否到达最后一个石头
状态：f[i][j]表示是否能最后一跳长度j跳到石头a[i]
转移：f[i][j]=f[k][j-1] OR f[k][j] OR f[k][j+1] | a[k]=a[i]-j
边界：f[0][0]=true
答案：or{f[n-1][j]}
1269 停在原地的方案数
从坐标1出发，每次可以向左一格、向右一格、原地不动 问 steps 次操作后停留在原地的方案总数
坐标+背包1维费用
状态：dp[i][j]表示走了 i 次以后, 走到坐标 j 的路径数
（j可能是负数但是范围有限是n，故可以限制其范围并坐标映射+n/2）
转移：dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] + dp[i - 1][j + 1]
边界：dp[0][0]=1
答案：dp[n-1][0]
子序型
又称为接龙型，传统的接龙动规做法，一般是告诉你一个接龙规则，让你找最长的龙
状态：dp[i]表示以下i标结尾的龙最长是多长
LCIS
状态：f[i]表示以下i标结尾的连续递增串最长是多长
转移：f[i]=f[i-1]+1|a[i]>a[i-1]
边界：f[i]=1
答案：max(dp[i])
LIS
状态：dp[i]表示以下i标结尾的龙最长是多长
转移：dp[i]=max{dp[j]+1|j<i&&nums[j]<nums[i]}
边界：dp[0..n-1]=1
答案：max(dp[i])
LIS
状态：f[i]表示以下i标结尾的龙最长是多长
转移：f[i]=max{1,f[j]+1|i<j and a[i]<a[j]}
LIS 的二分做法选择性的掌握即可，并不是所有的接龙型DP都可以用二分来优化
Russian Doll Envelopes
给定N个信封的长度和宽度。如果一个信封的长和宽都分别小于另一个信封的长和宽，则这个信封可以放入另一个信封。问最多嵌套多少个信封
Longest Continuous Increasing Subsequence II
四个方向，依然可以动态规划
Largest Divisible Subset
特殊点：需要一个额外的数组记录上一个位置的值
如果需要找到这个路径的话会麻烦一些，需要hashmap或倒推法
单词接龙问题
给一个单词集合，两个单词可以接在一起当且仅当前一个单词的后缀和后一个单词的前缀，能够重叠至少1个字符
每个单词可以且仅可以使用一次，请问最长接出来的龙的长度多少?
不同的子序列
给定一个小写字母组成的字符串S，问S中不同的非空子序列的个数
状态：f[i]表示以下标 i 字符结尾的不同子序列有多少个
转移：f[i]=sum{f[j]|a[i] not in f[j+1,i-1]}
边界：f[i]=1, a[i]是第一次出现
等差数列划分
子串型
核心：连续，Kadane 算法
在数组或滑动窗口中找到子串和的最大值或最小值的 O(N) 算法（可拓展到别的）
最大子数组和
状态：f[i]表示以下i标结尾的最大子数组和
转移：f[i]=nums[i]+max{0, f[i-1]}
边界：f[0]=nums[0]
答案：max{f[i]}
最长连续序列
状态：f[i]表示以下i标结尾的最长连续序列长度
转移：
f[i]=f[i-1]+1, nums[i]==nums[i-1]f[i]=1, nums[i]!=nums[i-1]
答案：max{f[i]}
最大子数组积
坐标型+状态型（需要知道来这里之前的一步的状态：最大/最小）
状态：f[i][0/1]表示以下i标结尾的最小/大子数组积
转移：
f[i][0]=min{nums[i], f[i-1][0]*nums[i], f[i-1][1]*nums[i]}}f[i][1]=max{nums[i], f[i-1][0]*nums[i], f[i-1][1]*nums[i]}}
边界：f[0]=nums[0]
答案：max{f[i][1]}
位运算型
&|^!
i是一个数字，也是一个状态
Counting Bits 比特位计数
求 0, 1, ..., n 每个数字的二进制1的个数
状态：f[i]表示数字i的1个数
转移：f[i]=f[i>>1]+(i&1)
写法二：最低设置位法
转移：f[i]=f[i & (i - 1)] + 1
多坐标
摘樱桃
摘樱桃 II