序列型
序列型
题目变种多，没有固定模板，见招拆招
分类
前缀型/序列型
- 背包型
- 划分型
- 双序型/匹配型
后缀型
对于博弈问题，每次都取头部的东西（边不可逆），再往后选，这样只能从后往前推
也适合于不确定终点的时候使用
给定一个序列
状态：f[i]表示前i个元素a[0],a[1],...,a[i-1]的某种性质
边界：f[0]表示空序列的性质
给定一个序列
状态：f[i]表示从i开头到结尾元素a[i],a[i+1],...,a[n-1]的某种性质
边界：f[n]表示空序列的性质
前缀型
Decode Ways
lc91. 即带限制的爬楼梯/fib
状态：f[i]表示前i个数字解密成字符串的方案数
转移：f[i]=f[i-1]|letter(i-1) + f[i-2]|letter(i-2,i-1)
边界：f[0]=1,f[1]=letter(1)
顺序：0-n
Decode Ways II
有一段由A-Z组成的字母串信息被加密成数字串
• 加密方式为:Aà1, Bà2, ..., Zà26
• 给定加密后的数字串S[0...N-1]，问有多少种方式解密成字母串 • 其中可能出现*字符，可以被替换成为1~9中的任何一个字符
状态：f[i]表示前i个数字解密成字符串的方案数
转移：f[i]=f[i-1]*letter(i-1) + f[i-2]*letter(i-2,i-1)
边界：f[0]=1,f[1]=letter(1)
顺序：0-n
Paint House
一共3个颜色，相邻两家不能颜色一样
lc256. Paint House
序列+状态
状态：f[i][j]表示前i个房子，第i-1是颜色j，最小花费
转移：
Paint House II
一共k个颜色，相邻两家不能颜色一样
状态：f[i][j]表示前i个房子，第i-1是颜色j，最小花费
转移：
O(nk2)
优化：每次要求出了j以外其他元素的最小值，加速方法，记录最小值和次小值O(nk)
Paint House III
m个房子，一共n个颜色，相邻几家颜色一样构成一个街区，要求构成target个街区最小花费
状态：f[i][j][k]表示前i个房子，第i-1是颜色j，构成k个街区，最小花费
转移：f[i][j][k]=min{f[i-1][j][k],min{f[i-1][x][k-1]}}+cost[i-1][j]
O(nk2)
优化：每次要求出了j以外其他元素的最小值，加速方法，记录最小值和次小值O(nk)
用b[i][k]表示f[i][?][k]的(1st,1stIdx,2st)，这样可以O1取得min
House Robber
不能偷相邻两家
两种理解思路，可以推出两种状态和对应的状态转移
状态：f[i]表示前i个房子的最大值（不限制i-1是否被抢）
转移：f[i]=min{f[i-1],f[i-2]+a[i-1]}
边界：f[0]=0,f[1]=a[0]
答案：f[n]
状态：f[i][j]表示前i个房子，i-1是否被抢为j，的最大值
转移：
f[i][1]=f[i-1][0]+a[i-1]f[i][0]=min{f[i-1][0],f[i-1][1]}
边界：f[0][j]=0
答案：Math.max{f[n][0], f[n][1]}
House Robber II
不能偷相邻两家，环型的，即首位不能同时被偷
化为1-n-1和0-n-2
Best Time To Buy And Sell Stock
只能买卖一次
状态：f[i][j]表示前i个股票，i-1是否有j，的最大值
转移：
f[i][0]=max{f[i-1][0],f[i-1][1]+v[i-1]}f[i][1]=max{f[i-1][1],0-v[i-1]}
答案：f[n][0]
方向：从0到N-1枚举j，即第几天卖
时刻保存当前为止（即0~j-1天）的最低价格P:
最大的P,-P即为答案
Best Time To Buy And Sell Stock II
可以买卖无限次
状态：f[i][j]表示前i个股票，i-1是否有j，的最大值
转移：
f[i][0]=max{f[i-1][0],f[i-1][1]+v[i-1]}f[i][1]=max{f[i-1][1],f[i-1][0]-v[i-1]}
Best Time To Buy And Sell Stock III
可以买卖2次
零一背包+状态
状态：f[i][k][j]表示前i个股票，买卖k次，i-1是否有j，的最大值
转移：
f[i][0]=max{f[i-1][0],f[i-1][1]+v[i-1]}f[i][1]=max{f[i-1][1],f[i-1][0]-v[i-1]}
Best Time To Buy And Sell Stock IV
可以买卖k次
状态：f[i][k][j]表示前i个股票，买卖k次，i-1是否有j，的最大值
转移：
f[i][0]=max{f[i-1][0],f[i-1][1]+v[i-1]}f[i][1]=max{f[i-1][1],f[i-1][0]-v[i-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或者一个变量即可
Minimum Adjustment Cost
给定数组A，每个元素是不超过100的正整数
• 将A中每个元素修改后形成数组B
• 要求B中任意两个相邻的元素的差不能超过Target
• 求最小修改代价，即|A[0]-B[0]| + ... + |A[n-1]-B[n-1]|不知道是多少就记录下来：序列加状态
状态：f[i][j]表示前i个位置，第i-1变成j，都符合条件，的最小花费
转移：f[i][j]=min{f[i-1][k]+abs(j-a[i-1])|abs(k-j)<=target, k in [1,100]}
边界：f[0][j]=0
染色问题(阿里)
有一个圆形被分成n个扇形，用m种颜色给每个扇形染色，相邻扇形颜色不 能相同，求方案总数(不考虑对称性)。由于这个数可能很大，因此只需返回方 案数模1e9 + 7。
LintCode 1444.
令dp[i]表示共 i 个扇形时，使用 m 种配色的上色方案数
分隔数组以得到最大和
状态：f[i]表示前i个位置，最大和
转移：f[i]=max{f[j]+(i-j)*max[j, i-1]}
边界：f[0]=0
总结
序列+状态型DP
当思考最后一步时，这一步的选择依赖于前一步的某种状态
Paint House
House Robber
当思考动态规划最后一步时，这一步的选择依赖于前一步的某种状态
初始化时，[0]代表前0个元素/前0天的情况
与坐标型动态规划区别
计算时，的代表前i个元素（即元素0~i-)的某种性质