线性 DP 最经典单串 给定一个无序的整数数组,找到其中最长上升子序列的长度。
示例:
输入: [10,9,2,5,3,7,101,18] 输出: 4 解释: 最长的上升子序列是 [2,3,7,101],它的长度是 4。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution {public : int lengthOfLIS (vector<int >& nums) { int maxLength=0 ; vector<int > dp (nums.size(),1 ) ; for (int i=0 ;i<nums.size ();i++) { for (int j=0 ;j<i;j++) { if (nums[i]>nums[j]&&dp[i]<(dp[j]+1 )) { dp[i]=dp[j]+1 ; } } maxLength=max (maxLength,dp[i]); } return maxLength; } };
最经典双串: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution {public : int longestCommonSubsequence (string text1, string text2) { int len1=text1.size (); int len2=text2.size (); int dp[len1+2 ][len2+2 ]; 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][j-1 ],dp[i-1 ][j]); } } } return dp[len1][len2]; } };
经典问题: