• 注意事项

  这道题和最多买卖两次是一模一样的思路就是把2换成k了但是还是有几个地方需要注意的

  1. 给的整数数组可能为0
  2. k其实没有很大，可以想一下，最多为n/2(n是数组的长度)

int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if(n == 0){
            return 0;
        }
        k = min(k, n/2);
        vector<vector<vector<int>>> dp(n+1,vector<vector<int>>(k+1, vector<int>(2, 0)));
        //dp[1][k][0] = 0 && dp[1][k][1] = -prices[0]
        for(int i = 0; i < k + 1; i++){
            dp[1][i][0] = 0;
            dp[1][i][1] = -prices[0];
        }
        for(int i = 2; i < n + 1; i++){
            for(int j = 1; j < k + 1; j++){
                dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i-1]);
                dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i-1]);
            }
        }
        return dp[n][k][0];
    }

• 注意事项

  含冷冻期，说明一个事儿：即如果你买了的话，你必须是i-2买的，不能是i-1了！！！

int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n == 0){
            return 0;
        }
        //尽可能多的完成交易，也就说不限制次数
        vector<vector<int>> dp(n+1, vector<int>(2, 0));
        dp[1][0] = 0;
        dp[1][1] = -prices[0];
        for(int i = 2; i < n + 1; i++){
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1]);
            dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i-1]);
        }
        return dp[n][0];
    }

• 注意事项

  有手续费而已，无非就是卖出的时候减去手续费，简单！

int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        if(n == 0){
            return 0;
        }
        vector<vector<int>> dp(n + 1, vector<int>(2, 0));
        dp[1][0] = 0;
        dp[1][1] = -prices[0];
        for(int i = 2; i < n + 1; i++){
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1]- fee);
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i-1]);
        }
        return dp[n][0];
    }

• 注意事项

  贪心足以，不用动态规划了！

int findLengthOfLCIS(vector<int>& nums) {
        int n = nums.size();
        int max_len = 1;
        int count = 1;
        for(int i = 1; i < n ; i++){
            if(nums[i] > nums[i-1]){
                count++;
                max_len = max(max_len, count);
            }else{
                count = 1;
            }
        }
        return max_len;
    }

• 这道题动态规划不太好想，如果画个图会好一点，因此我就随便在网上找一张图了。

  

  这张图对于理解二维dp数组很有帮助

  这里面$dp[i][j]$表示对于第一个数组前i个，和第二个数组前j个元素相等的数量，然后用一个max_com来存储个最大值，其实这种dp不太好想，还是画个dp来理解一下比较好

int findLength(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size();
        int n2 = nums2.size();
        int max_com = 0;
        vector<vector<int>> dp(n1+1, vector<int>(n2+1, 0));
        for(int i = 1; i < n1 + 1; i++){
            for(int j = 1; j < n2 + 1; j++){
                if(nums1[i-1] == nums2[j-1]){
                    dp[i][j] = dp[i-1][j-1] + 1;
                    max_com = max(max_com, dp[i][j]);
                }
            }   
        }
        return max_com;
    }

• 滑动窗口

  参考链接

int findLength(vector<int>& nums1, vector<int>& nums2) {
    int n1 = nums1.size();
    int n2 = nums2.size();
    return n1 > n2 ? sliding(nums2, nums1) : sliding(nums1, nums2);
}
int sliding(vector<int>& short_vec, vector<int>& long_vec){
    int n1 = short_vec.size();
    int n2 = long_vec.size();
    int max_repeat = 0;

    //短的和长的数组的最右边对齐
    for(int i = 1; i <= n1; i++){
        int tmp = get_repeat(short_vec, 0, long_vec, n2-i,i);
        cout<<"tmp1:"<<tmp<<endl;
        max_repeat = max(tmp, max_repeat);
    }

    //短的和长的数组的最左边对齐
    //以长数组的长度为参考
    for(int i = n2; i - n1>=0; i-- ){
        int tmp = get_repeat(short_vec, 0, long_vec, i-n1, n1);
        cout<<"tmp2:"<<tmp<<endl;
        max_repeat = max(tmp, max_repeat);
    }

    //短数组的右边和长数组的左边对齐
    //以短数组的长度为参考
    for(int i = n1; i >= 1; i--){
        int tmp = get_repeat(short_vec, n1-i, long_vec, 0, i);
        cout<<"tmp3:"<<tmp<<endl;
        max_repeat = max(tmp, max_repeat);
    }
    return max_repeat;
}

int get_repeat(vector<int>& short_vec, int i, vector<int>& long_vec, int j, int common_len){
    int max_repeat = 0;
    int count = 0;    
    for(int index = 0; index < common_len; index++){
        if(short_vec[i+index] == long_vec[j+index]){
            count++;
            max_repeat = max(count, max_repeat);
        }else{
            max_repeat = max(count, max_repeat);
            count = 0;
        }
    }
    return max_repeat;
} 

• 注意事项，这道题简单是简单，状态转移方程也不难。但是要记住这道题不是求得dp[n]！而是求dp数组的最大值

int maxSubArray(vector<int>& nums) {
        //这道题一眼dp不解释
        int n = nums.size();
        vector<int> dp(n + 1, INT_MIN);
        dp[1] = nums[0];
        for(int i = 2; i < n + 1; i++){
            dp[i] = max(dp[i-1]+nums[i-1], nums[i-1]);
        }
        int max_sum = INT_MIN;
        for(auto n : dp){
            max_sum = max(max_sum, n);
        }
        return max_sum;
    }

这道题第二次做的时候一时间没有想到还。之前我老是想着nums[i-1]与nums[i-2]做匹配，其实是不对的，因为相邻的两个数其实没什么关系，不能这样子比较

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n + 1, 1);
    for(int i = 2; i < n + 1; i++){
        for(int j = 1; j < i; j++){
            if(nums[i - 1] > nums[j - 1]){
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    int max_sub = 0;
    for(auto n:dp){
        max_sub = max(max_sub, n);
    }
    return max_sub;
}

int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n+1, 1);
    int tmp = nums[0];
    for(int i = 2; i < n + 1; i++){
        int tmp = 1;
        for(int j = 1; j < i; j++){
            if(nums[i-1] > nums[j-1]){
                tmp = max(tmp, dp[j] + 1);
            }
        }
        dp[i] = tmp;
    }
    sort(dp.begin(), dp.end(), std::greater<int>());
    return dp[0];
}

二分

时间复杂度nlogn

维护一个结果数组，如果当前元素比结果数组的值都大的的话，就追加在结果数组后面（相当于递增序列长度加了1）；否则的话用当前元素覆盖掉第一个比它大的元素(增长缓慢才可能是最长的)（这样做的话后续递增序列才有可能更长，即使并没有更长，这个覆盖操作也并没有副作用哈，当然这个覆盖操作可能会让最终的结果数组值并不是最终的递增序列值，这无所谓）

操作只有两个：覆盖和追加，只有大于最后一个元素才会追加，其他时候都是覆盖

//比较粗糙的二分，每次循环都求了res数组的大小，效率太低
 int lengthOfLIS(vector<int>& nums) {
     int n = nums.size();
     vector<int> res;
     res.push_back(nums[0]);
     int tmp = nums[0];
     for(int i = 1; i < n; i++){
         if(nums[i] > tmp){
             res.push_back(nums[i]);
             tmp = nums[i];
         }
         else if(tmp == nums[i]){
             continue;
         }
         else{
             int index = lower_bound(res.begin(), res.end(), nums[i]) - res.begin();
             cout<<"nums[i]:"<<nums[i]<<endl;
             cout<<"index:"<<index<<endl;
             res[index] = nums[i];
             int n = res.size();
             tmp = res[n-1];
         }
     }
     return res.size();
 }

//改进的二分
nt lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    vector<int> res;
    res.push_back(nums[0]);
    int count = 0;
    for(int i = 1; i < n; i++){
        int index = lower_bound(res.begin(), res.end(), nums[i]) - res.begin();
        //之前用的是upper_bound，结果[4,10,4,3,8,9]未通过
        if(index > count){
            res.push_back(nums[i]);
            count++;
        }else{
            res[index] = nums[i];
        }

    }
    return res.size();
}

• 最长公共子序列问题是一类问题，包括下面的583和712题，都是一样的

  公共子序列，打表就能做出来了！！典型的打表题

• 以下是代码部分

  int longestCommonSubsequence(string text1, string text2) {
      int n = text1.size();
      int m = text2.size();
      vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
      for(int i = 1; i < n + 1; i++){
          for(int j = 1; j < m + 1; 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[n][m];
  }