最大子数组和 最长递增子序列 最长公共子序列 编辑距离之复习dp
哥们记得当初刷dp题都做过,但哥们都忘了怎么做的了,来写个备忘录
最大子数组和
如果数组中没有大于0的数,就返回数组中最大的值
否则设一个num,遍历nums数组,如果num加一个数小于0,这个前缀和就可以整体扔掉,否则就更新num,使num成为新的前缀和,前缀和加下一个元素永远比不加前缀和大
更新前缀和的操作也和dp有点像
int maxSubArray(vector<int>& nums) {
int num = 0;
int ans = 0;
int min_val = INT_MIN;
int n = nums.size();
for(int i = 0;i < n;i++){
min_val = max(min_val,nums[i]);
if(num+nums[i]>0){
num += nums[i];
if(num > ans) ans = num;
}else num = 0;
}
if(min_val<0) return min_val;
else return ans;
}
最长递增子序列
先初始化每个dp都为一
递归每个数之前的数,看前面比它小的数i的dp[i] + 1 哪个更大
int lengthOfLIS(vector<int>& nums) {
int len = nums.size();
int dp[2505];
for (int i = 0; i < len; i++) {
dp[i] =1;
}
int max_value = 1;
for (int i = 1; i < len; i++) {
for (int j = i-1; j >=0 ; j--) {
if (nums[i]>nums[j]){
dp[i] = max(dp[i],dp[j]+1);
}
max_value = max(max_value,dp[i]);
}
}
return max_value;
}
最长公共子序列
你要想起来那个表
int longestCommonSubsequence(string text1, string text2) {
int len1 = text1.size();
int len2 = text2.size();
int dp[len1+1][len2+1];
memset(dp,0,sizeof(dp));
for (int i = 1; i <=len1; i++) {
for (int j = 1; j <= len2; j++) {
if (text1[i-1] == text2[j-1]) {dp[i][j] = dp[i-1][j-1]+1;}
else {dp[i][j] = max(dp[i-1][j],dp[i][j-1]);}
}
}
return dp[len1][len2];
}
编辑距离
一开始给dp的初始化很有意思,dp[i][j]的意思是第一个字符串的第i号第二个字符串的第j号,所以dp[i][0]要实现两个字符串相等就要进行i步插入
然后就开始dp
插入
i i
a b c d a b c d
j j
x y e x y e d
所以dp[i][j] = dp[i-1][j] +1,即继续判断第i-1和第j项
替换
i i
a b c d a b c d
j j
x y e x y d
所以dp[i][j] = dp[i-1][j-1] +1
删除
i i
a b c d a b c d
j j-1 j
x y e x y e(被删除)
仅仅是删除了,并没有保证删除后的两个字符一定相等
所以dp[i][j] = dp[i][j-1] +1
int minDistance(string word1, string word2) {
int len1 = word1.size()+1;
int len2 = word2.size()+1;
int dp[len1][len2];
memset(dp,0, sizeof(dp));
for (int i = 0; i < len1; i++) {
dp[i][0] = i;
}
for (int i = 0; i < len2; i++) {
dp[0][i] = i;
}
for (int i = 1; i < len1; i++) {
for (int j = 1; j <len2; j++) {
if (word1[i-1]==word2[j-1]){
dp[i][j] = dp[i-1][j-1];
} else {
dp[i][j] = 1+min(min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1]);
}
}
}
return dp[len1-1][len2-1];
}