2023年10月30日 - 动态规划13

300. 最长递增子序列

dp[i]以nums[i]为尾的最长递增子序列的长度

dp[i] 和 dp[j] ( 0 < j < i)有关

 class Solution {
 public:
     int lengthOfLIS(vector<int>& nums) {
         if (nums.size() <= 1) return nums.size();
         vector<int> dp(nums.size(), 1);
         int result = 0;
         for (int i = 1; i < nums.size(); i++) {
             for (int j = 0; j < i; j++) {
                 if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
             }
             result = max (result, dp[i]); // 取长的子序列
         }
         return result;
     }
 };

674. 最长连续递增序列

dp[i]只和dp[i - 1]有关

 class Solution {
 public:
     int findLengthOfLCIS(vector<int>& nums) {
         if (nums.size() == 0) return 0;
         int result = 1;
         vector<int> dp(nums.size() ,1);
         for (int i = 1; i < nums.size(); i++) {
             if (nums[i] > nums[i - 1]) { // 连续记录
                 dp[i] = dp[i - 1] + 1;
             }
             if (dp[i] > result) result = dp[i];
         }
         return result;
     }
 };

718. 最长重复子数组

dp[i][j] 以i - 1为尾的nums1和 以j - 1为尾的nums2的最长重复子数组长度

 class Solution {
 public:
     int findLength(vector<int>& nums1, vector<int>& nums2) {
         vector<vector<int>> dp (nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
         int result = 0;
         for (int i = 1; i <= nums1.size(); i++) {
             for (int j = 1; j <= nums2.size(); j++) {
                 if (nums1[i - 1] == nums2[j - 1]) {
                     dp[i][j] = dp[i - 1][j - 1] + 1;
                 }
                 if (dp[i][j] > result) result = dp[i][j];
             }
         }
         return result;
     }
 };