动态规划三

6/23

T53 最大子序和

1、这一题之前有贪心解法，但贪心解法虽然简洁，理解难度却比动态规划大

2、动态规划解法中，赋值dp[i]需要相当谨慎：既然是连续的，就要卡死结尾；而我又想要最大和，因此可以只要一个结尾，也可以加上左侧部队一起。这样万一左侧总和为负，就可以抛弃之

3、初始元素和result的初始赋值很重要，要考虑nums只有一个元素、初始元素为负数的情况，即便全数组都为负数，result也可以取最小的一个元素，而该元素可能为nums[0]

4、代码如下：

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> dp(nums.size(),0);
        int result = nums[0];

        if(nums.size() == 1)
            return result;
        //dp[i]表示数组[0...i]之间的以nums[i]结尾的具备最大和的连续子数组
        dp[0] = nums[0];
        for(int i = 1;i < nums.size();i++){
            dp[i] = max(nums[i],nums[i] + dp[i-1]);
            if(dp[i] > result)
              result = dp[i];
        }
            return result;
    }
};

T1035 不相交的线

1、不相交意味着：所有组合之间要么两个元素都大于对方两者，要么两个元素都小于

2、和上一题类似，若相等，加一；不相等，只取其一更新max。重要：之所以只取其一，是因为若新的两个元素都取，且队伍统一在左侧，必然会出现两线交叉情况，故舍弃

3、代码如下：

class Solution {
public:
    int maxUncrossedLines(vector<int>& nums1, vector<int>& nums2) {
      vector<vector<int>> dp(nums1.size() + 1,vector<int>(nums2.size() + 1,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;

                }else{
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
              return dp[nums1.size()][nums2.size()];
        }
    };

T1143 最长公共子序列

1、这一题很适合用来养成良好习惯，手搓时没想清楚边界问题一下就会暴露出来。首先，dp[i][j]代表的是长度为i j的两个数组的最长公共子序列的长度，那么坐标最大值就是i-1 j-1，这才是当前需要比较是否相等的值；其次，遍历时也应该把结尾遍历到，而非常见的取小于号；最后，dp[0][0]是无意义的，没有坐标为-1的元素，这也是最终循环统一右移一位的原因

2、不要死套公式，这一题既没有连续的要求，又无单调性要求，毫无必要卡死“以…为结尾”这一要求，这样的序列是可以灵活跳脱的

3、当心：并不是不等就不管它或直接赋值上一层，即便最后两个元素不等，它们也可以分别加入与对面序列进行灵活取公，也就是dp[i-1][j] dp[i][j-1]，这点思考很重要，容易漏掉。顺便，string是可以直接按照char取坐标位的，无需拆入新的容器，也可以直接调用size()方法

4、代码如下：

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size() + 1,vector<int>(text2.size() + 1,0));
        //dp[i][j]代表在text1[0...i-1]和text2[0...j-1]中最长公共子序列的长度
        for(int i = 1;i <= text1.size();i++){
            for(int j = 1;j <= text2.size();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[text1.size()][text2.size()];
    }
};

6/20

T718 最长重复子数组

1、这道题有滑动窗口解法，二轮复习时重点研究

2、这一题关键在于拓展思路：既然涉及两个数组，那么严肃上上道经典题目，采取尾部比较方法，直接让dp[i][j]利用二维来解决双数组问题即可，非常聪明的做法

3、本题还有滚动数组一维解法，有时间可以探究一下

4、代码如下：

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;
    }
};

T674 最长连续递增序列

1、学会了上一题后，这题稍微变通一下就自己写出来啦～主要区别：既然要求连续递增，就只需关心i相邻的前一个j，即i-1就够了，因为以nums[i]结尾的序列必须和前面的序列连续。其它部分例如比较结尾元素大小等和上一题均如出一致

2、代码如下：

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        //dp[i]表示以nums[i]结尾的连续递增子序列的最大长度
        vector<int> dp(nums.size(),1);
        int result = 0;
        if(nums.size() == 1)
        return 1;
        for(int i = 1;i < nums.size();i++){
            if(nums[i-1] < nums[i])
            dp[i] = dp[i-1] + 1;


            if(dp[i] > result)
            result = dp[i];
        }


        return result;

    }
};

【重要】T300 最长递增子序列

1、这一题看着代码短，没有接触过类似问题的话思路很难想到，是一系列经典思维的开端：固定某个序列的结尾值，按照右侧截断数组的方式从前往后比较

2、关键：dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度，if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

3、假如小于呢？是否会漏掉情况？实则不会，因为每个i之前的所有j都遍历过，因此假设某个j对应的最长子序列是1 3 5 7 9，nums[i] = 8，虽然在个情况下被舍弃了，但j稍微往前走一点，最长子序列为1 3 5 7 时就可以纳入nums[i]形成1 3 5 7 8序列，dp[i]依旧会被正确更新

4、代码如下：

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);
            }
            if (dp[i] > result) result = dp[i]; // 取长的子序列
        }
        return result;
    }
};

6/18

T309买卖股票的最佳时期含冷冻期

1、这一题比较难，复杂度较高，摘录随想录分析如下： 达到买入股票状态（状态一）即：dp[i][0]，有两个具体操作： 操作一：前一天就是持有股票状态（状态一），dp[i][0] = dp[i - 1][0] 操作二：今天买入了，有两种情况 前一天是冷冻期（状态四），dp[i - 1][3] - prices[i] 前一天是保持卖出股票的状态（状态二），dp[i - 1][1] - prices[i] dp[i][0] = max(dp[i - 1][0], dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]);

达到保持卖出股票状态（状态二）即：dp[i][1]，有两个具体操作： 操作一：前一天就是状态二 操作二：前一天是冷冻期（状态四） dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);

达到今天就卖出股票状态（状态三），即：dp[i][2] ，只有一个操作： 昨天一定是持有股票状态（状态一），今天卖出 即：dp[i][2] = dp[i - 1][0] + prices[i];

达到冷冻期状态（状态四），即：dp[i][3]，只有一个操作： 昨天卖出了股票（状态三） dp[i][3] = dp[i - 1][2];

2、状态转移图

3、注意这里的每一个状态，例如状态一，是持有股票股票状态并不是说今天一定就买入股票，而是说保持买入股票的状态即：可能是前几天买入的，之后一直没操作，所以保持买入股票的状态

4、代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (n == 0) return 0;
        vector<vector<int>> dp(n, vector<int>(4, 0));
        dp[0][0] -= prices[0]; // 持股票
        for (int i = 1; i < n; i++) {
            dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]));
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
            dp[i][2] = dp[i - 1][0] + prices[i];
            dp[i][3] = dp[i - 1][2];
        }
        return max(dp[n - 1][3], max(dp[n - 1][1], dp[n - 1][2]));
    }
};

T188 买卖股票的最佳时机四

1、上一题进阶版！实则发现多状态转移规律后很简单，用一个for循环上公式即可

2、关键：除了0以外，偶数就是卖出，奇数就是买入

3、核心状态转移方程： for (int j = 0; j < 2 * k - 1; j += 2) { dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]); dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]); }

4、代码：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {


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

6/17

【重要】T123 买卖股票的最佳时机三

1、这一题级别为困难，的确有两个不好解决的地方：首先两笔交易不能重合，这样我们就不能直接在切割时保留一个min，这样无法确保中间无重叠区域；其次，第二笔交易未必是相邻非负差值，很可能买入日期涉及到前面的日子，无法直接直觉解题

2、官方解法：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int buy1 = -prices[0], sell1 = 0;
        int buy2 = -prices[0], sell2 = 0;
        for (int i = 1; i < n; ++i) {
            buy1 = max(buy1, -prices[i]);
            sell1 = max(sell1, buy1 + prices[i]);
            buy2 = max(buy2, sell1 - prices[i]);
            sell2 = max(sell2, buy2 + prices[i]);
        }
        return sell2;
    }
};

3、关键题解摘录：

4、这一题是少见的具备超过两个状态，且转移方程也有多个的题目，类似计算机网络里的一些状态转移传输逻辑

5、困惑点一：为何要每次取最大值，新买入了股票一定是扣钱的，理应变小一些，为何还强行要取最大值

答案：例如两个buy的方程，对比的实际上是什么时候买入更划算，负数绝对值更小，第三天价格3的话-3就比第一题价格5时的-5划算；sell方程则

6、困惑点二：为何要按照这样的顺序列方程，我换一下顺序可以吗

答案：不能，需要使用更新后的值

7、该题动态规划法总体思路仍较为抽象，需要严格的数学证明、逻辑推导，待解决+听详细网课

T121 买卖股票的最佳时机二

1、之前贪心专题涉及过，此次采用动态规划

2、这一题的动态规划意外地比贪心思路简单，甚至比第一题思路更清晰：截止某日的最大利润等于截止前一日的最大利润+非负相邻增值，时间复杂度也很好，不需要像贪心那样利用上升坡理解抽象思维

3、代码如下，AC：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //dp[i]表示截止到第i日的最大利润
        vector<int> dp(prices.size());
        dp[0] = 0;
        for(int i = 1;i < prices.size();i++){
            dp[i] = dp[i-1] + max(0,prices[i] - prices[i-1]);
        }


        return dp[prices.size() - 1];
    }
};

T121 买卖股票的最佳时机

1、这一题我第一眼觉得和贪心很像，但既然在动态规划专题，选择动态规划的做法。我的思路是定义一个“最迟交易日”，然后根据是否在最后一天交易来构建状态方程，同时维护一个最小值。这一点和背包问题中单拎出来一个物品是否纳入很像

2、当心：变量命名不要和标准库函数名重合，例如min

3、我的代码AC如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
    //dp[i]表示最迟在第i天卖出这只股票所能获得的最大利润
    vector<int> dp(prices.size());
    dp[0] = 0;
    int myMin = prices[0];
    for(int i = 1;i < prices.size();i++){
        dp[i] = max(dp[i-1],prices[i] - myMin);
        myMin = min(myMin,prices[i]);
    }
      return dp[prices.size()-1];
    }
};

4、注意：股票系列的几道题，未来贪心方法也全部探索梳理一遍

6/16

【重要】T337打家劫舍三

1、…..还有三？谁家小区房屋排列成二叉树形状

2、传统递归方法可解决（后序遍历最佳，配合函数返回值）

3、若用动态规划，有一定难度，需要对一颗树的状态建模：dp数组（dp table）以及下标的含义：下标为0记录不偷该节点所得到的的最大金钱，下标为1记录偷该节点所得到的的最大金钱

4、递归方法（含时空复杂度优化）：

class Solution {
public:
    unordered_map<TreeNode* , int> umap; // 记录计算过的结果
    int rob(TreeNode* root) {
        if (root == NULL) return 0;
        if (root->left == NULL && root->right == NULL) return root->val;
        if (umap[root]) return umap[root]; // 如果umap里已经有记录则直接返回
        // 偷父节点
        int val1 = root->val;
        if (root->left) val1 += rob(root->left->left) + rob(root->left->right); // 跳过root->left
        if (root->right) val1 += rob(root->right->left) + rob(root->right->right); // 跳过root->right
        // 不偷父节点
        int val2 = rob(root->left) + rob(root->right); // 考虑root的左右孩子
        umap[root] = max(val1, val2); // umap记录一下结果
        return max(val1, val2);
    }
};

5、动态规划方法：

class Solution {
public:
    int rob(TreeNode* root) {
        vector<int> result = robTree(root);
        return max(result[0], result[1]);
    }
    // 长度为2的数组，0：不偷，1：偷
    vector<int> robTree(TreeNode* cur) {
        if (cur == NULL) return vector<int>{0, 0};
        vector<int> left = robTree(cur->left);
        vector<int> right = robTree(cur->right);
        // 偷cur，那么就不能偷左右节点。
        int val1 = cur->val + left[0] + right[0];
        // 不偷cur，那么可以偷也可以不偷左右节点，则取较大的情况
        int val2 = max(left[0], left[1]) + max(right[0], right[1]);
        return {val2, val1};
    }
};

T231 打家劫舍二

1、和初始题目的主要区别：屋子成环，之前的情况一被融合

2、变化不大，代码如下：

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.size() == 0) return 0;
        if (nums.size() == 1) return nums[0];
        int result1 = robRange(nums, 0, nums.size() - 2); // 情况二
        int result2 = robRange(nums, 1, nums.size() - 1); // 情况三
        return max(result1, result2);
    }
    // 198.打家劫舍的逻辑
    int robRange(vector<int>& nums, int start, int end) {
        if (end == start) return nums[start];
        vector<int> dp(nums.size());
        dp[start] = nums[start];
        dp[start + 1] = max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[end];
    }
};