DP 单串 - wenzhoullq/leetcode GitHub Wiki
dp字符串
以字符串形式求dp是非常常见的题目，它的精髓在于，如果是连续的则是枚举从这个字符串结尾开始到开头；如果是子序列的话，那么则划分为取和不取，dp的设计为dp[len][26],当然可以压缩到dp[26]，然后更新dp[s.charAt(i)]的数据。
题目
- 子序列
long[][] dp = new long[len][26];
dp[0][str[0]-'a'] = 1;
for(int i = 1 ; i < len ;i++){
for(int j = 0; j < 26;j++){
}
dp[i][str[i]-'a'] =;
}
long ans = 0 ;
for(int i = 0 ; i < 26 ; i++){
ans= (ans+dp[len-1][i])%mod;
}
return (int)(ans);
- 子数组
dp_O(k) - 多状态
依赖于前面发生过的k个且多状态
题目
2266. 统计打字方案数(值得注意的是,遍历从后往前，遇到不满足的直接continue out)
- 单调队列优化
当k=n且n=1e5时暴力枚举会失效,因此需要单调队列优化
dp_O(1)
依赖于前面发生过的一个
其他
因为我们要枚举XX（如字符） 所以我们第二维定义为字符
压缩数组到一维，就可以抽象出题型为 先找最大值，再更新最大值
题目
1411. 给 N x 3 网格图涂色的方案数 (难点在于状态的设计 和 转移方程)
2327. 知道秘密的人数(dp的设计是增加量而不是现存量)
P4310 绝世好题 位运算的时候，是对所有的进行更新
最长上升子序列（lis）
- dp[n-1]依赖于dp[n-2]
舔狗一无所有 这题是依赖两个部分:如dp[i-1][0] 依赖于i-1是0和i-1不是0,i-1不是0很容易理解，但是i-1是0的话,那么依赖于i-2不是0了
模板
lis是最经典的单串问题，根据分析可知，它是依赖于dp_O(1)同时它还是依赖于dp[0->i-1]的,从dp[0->i-1]中寻找满足题意的dp[j]于dp[i]进行比较；
如果遇到多维度比较，则先让一个维度排列好
如果是放盒子之类的,如果求最大到最小，其实也可以从最小到最大排序
！！！！注意： dp[i]的含义是 以i为结尾的最长上升子序列，并非在[0,i]之间的最长上升子序列
- 模板一
int[] dp;
for(int i=0;i<len;i++) dp[i]=//初始化dp
for(int i=0;i<len;i++){
for(int j=0;j<i;j++){
if(j满足题意)
{
dp[i]=Math.max(dp[j],dp[i]);
}
dp[i] +=;
ans=Math.max(ans,dp[i]);
}
}
- 模板二
如果时间复杂度要求在O(log n),那么出现二分模板
int[] tail=new int[nums.length];
int length=0;
for(int i=0;i<nums.length;i++){
int left=0,right=length;
while(left<right){
int mid=(left+right)/2;
if(tail[mid]<nums[i]) left=mid+1;
else right=mid;
}
tail[left]=nums[i];
if(right==length){
length++;
}
}
- 题目
导弹拦截 最长递增子序列（非严格递增）的长度=最长递减子序列的个数
P1091 合唱队形 左右取
435. 无重叠区间穿了衣服的lis,但是由于时间复杂度的问题只能用贪心求解
1691. 堆叠长方体的最大高度(因为可以翻转，所以对c[i]进行排序
2111. 使数组 K 递增的最少操作次数(分组lis)
状态机
状态机问题是依赖于dp_O(1)且依赖于dp[i-1],因此甚至可以将空间复杂度优化到O(1)
在股票问题中，如果没有买卖次数的话，那么dp就是第i-1的持仓和空仓状态，但是如果有买卖次数的话，dp状态分为 第N次买和第N次卖,值得注意的是，我们还是采用持仓和空仓描述状态，但是空仓的话，你是第N次交易空仓是第N次交易持仓得来的，而非第N-1次持仓得来的。
打家劫舍也同理，分为打了和没打，只是依赖的可能是dp[i-2]
模板
//dp初始化
dp[0][1]=-prices[0];
for(int i=1;i<=len;i++){
dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i-1]);
dp[i][1]=Math.max(dp[i-1][0]-prices[i-1],dp[i-1][1]);
}
题目
- 股票问题
- 打家劫舍
213. 打家劫舍 II 分为第一个打了和第一个没打
337. 打家劫舍 III 树形DP 自底向上
740. 删除并获得点数 构造处理一下成打家劫舍系列
最大子串和(Kadane算法)
kadane算法是求最大的连续子串，因为依赖的是dp[i-1]，所以空间压缩到常量,最主要的是遇到不满足的就重启
模板
dp[i]=max(dp[i-1]+nums[i-1],nums[i-1]);
题目
152. 乘积最大子数组 还得维护一个最小值
918. 环形子数组的最大和 针对环形的最大子串，还得求一个最小的和
1186. 删除一次得到子数组最大和 维护一个删除1次的数组
1191. K 次串联后最大子数组之和 分类讨论
面试题 17.24. 最大子矩阵 压缩到一维后是kadane
其他
也是依赖于dp_O(1),但是不太方便分类,就归到一起