哥们记得当初刷dp题都做过，但哥们都忘了怎么做的了，来写个备忘录
最大子数组和
如果数组中没有大于0的数，就返回数组中最大的值
否则设一个num，遍历nums数组，如果num加一个数小于0，这个前缀和就可以整体扔掉，否则就更新num，使num成为新的前缀和，前缀和加下一个元素永远比不加前缀和大
更新前缀和的操作也和dp有点像

int maxSubArray(vector& 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& 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 dj            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 dj              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 dj             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 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];}