Leetcode 刷题笔记-Leetcode 101 第7章 动态规划

Leetcode 刷题笔记-Leetcode 101 第7章 动态规划

动态规划

动态规划和其它遍历算法（如深/广度优先搜索）都是将原问题拆成多个子问题然后求解，他们之间最本质的区别是，动态规划保存子问题的解，避免重复计算。解决动态规划问题的关键是找到状态转移方程，这样我们可以通过计算和储存子问题的解来求解最终问题。同时也可以对动态规划进行空间压缩，起到节省空间消耗的效果。

基本动态规划：一维

Leetcode 70

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

class Solution {
public:
    int climbStairs(int n) {
        vector<int> num(n+1);
        if(n <= 2){
            return n;
        }
        else{
            num[1] = 1;
            num[2] = 2;
            for(int i=3;i<=n;++i){
                num[i] = num[i-1] + num[i-2];
            }
        }
        return num[n];
    }
};

分析：num[i]表示在第 i阶的方法数，则到达第 i阶的方法是到达第 i-1阶的方法和到达第 i-2阶的方法数之和。因此 num[i] = num[i-1] + num[i-2]。判断边界条件即可。

一遍AC

Leetcode 198

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统， 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n+1);
        if(n == 1){
            return nums[0];
        }
        else if(n == 2){
            return max(nums[0],nums[1]);
        }
        dp[1] = nums[0];
        dp[2] = max(nums[0],nums[1]);
        for(int i=3;i<=n;++i){
            dp[i] = max(dp[i-1],dp[i-2] + nums[i-1]);
        }
        return dp[n];
    }
};

分析：定义一个数组 dp，dp[i]表示抢劫到第i个房子时，可以抢劫的最大数量。我们考虑 dp[i]，此时可以抢劫的最大数量有两种可能，一种是我们选择不抢劫这个房子，此时累计的金额即为 dp[i-1]；另一种是我们选择抢劫这个房子，那么此前累计的最大金额只能是 dp[i-2]。因此本题的状态转移方程为 dp[i] = max(dp[i-1],nums[i-1] + dp[i-2])。然后判断边界条件即可。

一遍AC

Leetcode 413

给定一个数组，求这个数组中连续且等差的子数组一共有多少个

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        if(n == 1 || n == 2){
            return 0;
        }
        vector<int>dp(n+1);
        dp[0] = 0;
        dp[1] = 0;
        dp[2] = 0;
        for(int i=2;i < n;++i){
            if(nums[i] - nums[i-1] == nums[i-1] - nums[i-2]){
                dp[i+1] = dp[i] + 1;
            }
        }
        return accumulate(dp.begin(),dp.end(),0);
    }
};

分析：这道题略微特殊，因为要求是等差数列，可以很自然的想到子数组必定满足 num[i] - num[i-1] = num[i-1] - num[i-2]。然而由于我们对于 dp数组的定义通常为以 i结尾的，满足某些条件的子数组数量，而等差子数组可以在任意一个位置终结，因此此题在最后需要对 dp数组求和。

错误：最开始写的时候越界了

基本动态规划：二维

Leetcode 64

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dp(m,vector<int>(n,0));
        dp[0][0] = grid[0][0];
        for(int i=1;i<m;++i){
            dp[i][0] = dp[i-1][0] + grid[i][0];
        }
        for(int j=1;j<n;++j){
            dp[0][j] = dp[0][j-1] + grid[0][j];
        }
        for(int i=1;i<m;++i){
            for(int j=1;j<n;++j){
                dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j];
            }
        }
        return dp[m-1][n-1];
    }
};

分析：定义一个同样是二维的 dp数组，其中 dp[i][j]表示从左上角开始到 (i, j)位置的最优路径的数字和。因为每次只能向下或者向右移动，我们可以很容易得到状态转移方程 dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]，其中 grid表示原数组。

错误：注意区间，开多大的 dp数组以及怎么进行状态转移，不要把自己转蒙。

Leetcode 542

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。两个相邻元素间的距离为 1 。

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m = mat.size();
        int n = mat[0].size();
        vector<vector<int>> dp(m,vector<int>(n,0));
        if(mat[0][0] == 0){
            dp[0][0] = 0;
        }
        else{
            dp[0][0] = 10002;
        }

        for(int i=1;i<m;++i){
            if(mat[i][0] == 0){
                dp[i][0] = 0;
            }
            else{
                dp[i][0] = dp[i-1][0] + 1;
            }
        }
        for(int j=1;j<n;++j){
            if(mat[0][j] == 0){
                dp[0][j] = 0;
            }
            else{
                dp[0][j] = dp[0][j-1] + 1;
            }
        }
        for(int i=1;i<m;++i){
            for(int j=1;j<n;++j){
                if(mat[i][j] == 0){
                    dp[i][j] = 0;
                }
                else{
                    dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + 1;
                }
            }
        }
        for(int i=m-2;i>=0;--i){
            if(mat[i][n-1] == 0){
                dp[i][n-1] = 0;
            }
            else{
                dp[i][n-1] = min(dp[i][n-1],dp[i+1][n-1] + 1);
            }
        }
        for(int j=n-2;j>=0;--j){
            if(mat[m-1][j] == 0){
                dp[m-1][j] = 0;
            }
            else{
                dp[m-1][j] = min(dp[m-1][j],dp[m-1][j+1] + 1);
            }
        }
        for(int i=m-2;i>=0;--i){
            for(int j=n-2;j>=0;--j){
                if(mat[i][j] != 0){
                    dp[i][j] = min(dp[i][j],min(dp[i+1][j],dp[i][j+1])+1);
                }
            }
        }
        return dp;
    }
};

分析：从左上到右下进行一次动态搜索，再从右下到左上进行一次动态搜索。两次动态搜索即可完成四个方向上的查找。

错误：看了一下题解的思路，还是有点不敢想。另外要细心，注意越界！！！

Leetcode 221

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        int maxside = 0;
        for(int i=1;i<=m;++i){
            for(int j=1;j<=n;++j){
                if(matrix[i-1][j-1] == '1'){
                    dp[i][j] = min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j])) + 1;
                }
                maxside = max(maxside,dp[i][j]);
            }
        }
        return maxside * maxside;
    }
};

分析：dp[i][j]表示以 (i, j)为右下角的全由 1构成的最大正方形边长。

错误：状态转移方程没有想太好。

分割类型题

对于分割类型题，动态规划的状态转移方程通常并不依赖相邻的位置，而是依赖于满足分割条件的位置。

Leetcode 279

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n+1,100000000);
        dp[0] = 0;
        for(int i=1;i<=n;++i){
            for(int j=1;j*j<=i;++j){
                dp[i] = min(dp[i],dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
};

分析：dp[i]表示数字 i最少可以由几个完全平方数相加构成。

错误：没有思路

Leetcode 91

输入是一个由数字组成的字符串，输出是满足条件的解码方式总数。

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        if(s[0] == '0'){
            return 0;
        }
        if(n == 1){
            return 1;
        }
        vector<int>dp(n+1,1);
        int prev = s[0] - '0';
        for(int i=2;i<=n;++i){
            int cur = s[i-1] - '0';
            if((prev == 0 || prev > 2) && cur == 0){
                return 0;
            }
            if((prev == 1) || (prev == 2 && cur < 7)){
                if(cur){
                    dp[i] = dp[i-1] + dp[i-2];
                }
                else{
                    dp[i] = dp[i-2];
                }
            }
            else{
                dp[i] = dp[i-1];
            }
            prev = cur;
        }
        return dp[n];
    }
};

分析：dp[i]表示以当前第i个位置上的数字为结尾的表示方法总数。dp[i]取决于两个数字，当前的数字和前一个数字。如果当前数字是 0，而前一个数字不是 1或者 2，说明这两个数字不可能构成字符，因此直接返回 0。如果前一个数字是 1，当前的数字是什么都行，或者前一个数字是 2，而当前的数字是 0-6的某一个数，说明这两个能构成一种组合。同时如果当前的数字不是 0，那么这个数字自己也能构成一种。如果前一个数字是其他，说明不能和当前的数字产生关系了，就只能是当前的数字自己了。

错误：不明白

Leetcode 139

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int n = s.size();
        vector<bool> dp(n+1,false);
        dp[0] = true;
        for(int i=1;i<=n;++i){
            for(const string & word : wordDict){
                int len = word.size();
                if(i >= len && s.substr(i-len,len) == word){
                    dp[i] = dp[i] || dp[i-len];
                }
            }
        }
        return dp[n];
    }
};

分析：类似于完全平方数分割问题，这道题的分割条件由集合内的字符串决定，因此在考虑每个分割位置时，需要遍历字符串集合，以确定当前位置是否可以成功分割。注意对于位置0，需要初始化值为真。

子序列问题

对于子序列问题，第一种动态规划方法是，定义一个 dp数组，其中 dp[i]表示以 i结尾的子序列的性质。在处理好每个位置后，统计一遍各个位置的结果即可得到题目要求的结果。第二种动态规划方法是，定义一个 dp数组，其中 dp[i]表示到位置 i为止的子序列的性质，并不必须以 i结尾。这样 dp数组的最后一位结果即为题目所求，不需要再对每个位置进行统计。

Leetcode 300

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n+1,1);
        dp[0] = 0;
        for(int i=1;i<=n;++i){
            for(int j=0;j<i;j++){
                if(nums[i-1] > nums[j]){
                    dp[i] = max(dp[i],dp[j+1]+1);
                }
            }
        }
        return *max_element(dp.begin(),dp.end());
    }
};

分析： dp[i]表示以 i结尾的子序列的性质。简单动态规划即可。

错误：下标指代不清，初始化应该全部为1

Leetcode 1143

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0 。

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

分析：建立一个二维数组 dp，其中 dp[i][j]表示到第一个字符串位置 i为止、到第二个字符串位置 j为止、最长的公共子序列长度。

错误：没想到是二维的动态规划。

背包问题

给定一个正整数数组，求是否可以把这个数组分成和相等的两部分。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int sum = accumulate(nums.begin(),nums.end(),0);
        if(sum % 2 == 1){
            return false;
        }
        sum /= 2;
        vector<vector<int>> dp(n+1,vector<int>(sum+1,false));
        dp[0][0] = true;
        for(int i=1;i<=n;++i){
            for(int j=0;j<=sum;++j){
                if(j < nums[i-1]){
                    dp[i][j] = dp[i-1][j];
                }
                else{
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[n][sum];
    }
};

分析：背包问题，价值是一半，背包容量没有限制。比较重要的是 dp[0][0] =true，后续的判断都是从这个 true继承过来的。

错误：思路不够完善

Leetcode 474

给你一个二进制字符串数组 strs 和两个整数 m 和 n ，请你找出并返回 strs 的最大子集的长度，该子集中最多有 m 个 0 和 n 个 1

class Solution {
public:
    static vector<int> getzerosandones(string &str){
        vector<int> result(2);
        int n = str.size();
        for(int i=0;i<n;++i){
            if(str[i] == '0'){
                ++result[0];
            }
            else{
                ++result[1];
            }
        }
        return result;
    }
    int findMaxForm(vector<string>& strs, int m, int n) {
        int l = strs.size();
        vector<vector<vector<int>>> dp(l+1,vector<vector<int>>(m+1,vector<int>(n+1,0)));
        for(int i=1;i<=l;++i){
            vector<int> && zerosones = getzerosandones(strs[i-1]);
            int zero = zerosones[0];
            int one = zerosones[1];
            for(int j=0;j<=m;++j){
                for(int k=0;k<=n;++k){
                    dp[i][j][k] = dp[i-1][j][k];
                    if(j >= zero && k >= one){
                        dp[i][j][k] = max(dp[i][j][k],dp[i-1][j-zero][k-one]+1);
                    }
                }
            }
        }
        return dp[l][m][n];
    }
};

分析：三维的背包问题，要同时考虑两个背包的容量。

错误：还是不理解

Leetcode 322

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1 ，可以认为每种硬币的数量是无限的。

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<vector<int>> dp(n+1,vector<int>(amount+1,amount+1));
        dp[0][0] = 0;
        for(int i=0;i<=amount;++i){
            for(int j=1;j<=n;++j){
                if(coins[j-1] <= i){
                    dp[j][i] = min(dp[j-1][i],dp[j][i-coins[j-1]]+1);
                }
                else{
                    dp[j][i] = dp[j-1][i];
                }
            }
        }
        return dp[n][amount] == amount+1 ? -1 : dp[n][amount];
    }
};

分析：完全背包问题。

错误：就是不理解

字符串编辑

Leetcode 72

给定两个字符串，已知你可以删除、替换和插入任意字符串的任意字符，求最少编辑几步可以将两个字符串变成相同。

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(int i=0;i<=m;++i){
            dp[i][0] = i;
        }
        for(int j=0;j<=n;++j){
            dp[0][j] = j;
        }
        for(int i=1;i<=m;++i){
            for(int j=1;j<=n;++j){
                if(word1[i-1] == word2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }
                else{
                    dp[i][j] = min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j])) + 1;
                }
            }
        }
        return dp[m][n];
    }
};

分析：使用一个二维数组 dp[i][j]，表示将第一个字符串到位置 i为止，和第二个字符串到位置 j为止，最多需要几步编辑。当第 i位和第 j位对应的字符相同时，dp[i][j]等于 dp[i-1][j-1]；当二者对应的字符不同时，修改的消耗是 dp[i-1][j-1]+1，插入 i位置/删除 j位置的消耗是 dp[i][j-1] + 1，插入 j位置/删除 i位置的消耗是 dp[i-1][j] + 1。

错误：初始化没有做好。

Leetcode 650

给定一个字母A，已知你可以每次选择复制全部字符，或者粘贴之前复制的字符，求最少需要几次操作可以把字符串延展到指定长度。

class Solution {
public:
    int minSteps(int n) {
        vector<int> dp(n+1,0);
        for(int i=2;i<=n;++i){
            dp[i] = i;
            for(int j=2;j * j <= i;++j){
                if(i % j == 0){
                    dp[i] = dp[j] + dp[i/j];
                    break;
                }
            }
        }
        return dp[n];
    }
};

分析：我们使用一个一维数组dp，其中位置i表示延展到长度i的最少操作次数。对于每个位置j，如果j可以被i整除，那么长度i就可以由长度j操作得到，其操作次数等价于把一个长度为1的A延展到长度为i/j。因此我们可以得到递推公式dp[i] = dp[j] + dp[i/j]

错误：还是不会想。

Leetcode 10

给定一个字符串和一个正则表达式，求该字符串是否可以被匹配。

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size();
        int n = p.size();
        vector<vector<bool>> dp(m+1,vector<bool>(n+1,false));
        dp[0][0] = true;
        for(int i=1;i<=n;++i){
            if(p[i-1] == '*'){
                dp[0][i] = dp[0][i-2];
            }
        }
        for(int i=1;i<=m;++i){
            for(int j=1;j<=n;++j){
                if(p[j-1] == '.'){
                    dp[i][j] = dp[i-1][j-1];
                }
                else if (p[j-1] != '*') {
                    dp[i][j] = dp[i-1][j-1] && p[j-1] == s[i-1];
                }
                else if (p[j-2] != s[i-1] && p[j-2] != '.') {
                    dp[i][j] = dp[i][j-2];
                } 
                else {
                    dp[i][j] = dp[i][j-1] || dp[i-1][j] || dp[i][j-2];
                }
            }
        }
        return dp[m][n];
    }
};

分析：使用一个二维数组 dp，其中 dp[i][j]表示以 i截止的字符串是否可以被以 j截止的正则表达式匹配。

错误：没有思路

股票交易

Leetcode 121

给定一段时间内每天某只股票的固定价格，已知你只可以买卖各一次，求最大的收益。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int sell = 0, buy = INT_MIN;
        for (int i = 0; i < prices.size(); ++i) {
            buy = max(buy, -prices[i]);
            sell = max(sell, buy + prices[i]);
        }
        return sell;
    }
};

分析：遍历一次就行，记录一下最小的价格，然后遍历到每个价格的时候看看是不是比这个价格更大就行了。

错误：简单的问题也不会想了。。。

Leetcode 188

给定一段时间内每天某只股票的固定价格，已知你只可以买卖各 k次，且每次只能拥有一支股票，求最大的收益。

Leetcode 309

给定一段时间内每天某只股票的固定价格，已知每次卖出之后必须冷却一天，且每次只能拥有一支股票，求最大的收益。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n == 0){
            return 0;
        }
        vector<int> buy(n),sell(n),s1(n),s2(n);
        s1[0] = buy[0] = -prices[0];
        sell[0] = s2[0] = 0;
        for(int i=1;i<n;++i){
            buy[i] = s2[i-1] - prices[i];
            s1[i] = max(buy[i-1],s1[i-1]);
            sell[i] = max(buy[i-1],s1[i-1]) + prices[i];
            s2[i] = max(s2[i-1],sell[i-1]);
        }
        return max(sell[n-1],s2[n-1]);
    }
};

分析：状态机求解

错误：完全不懂

练习

Leetcode 213

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 1){
            return nums[0];
        }
        else if(n == 2){
            return max(nums[0],nums[1]);
        }
        vector<int> dp(n+1);
        int answer_a;
        dp[0] = dp[1] = dp[2] = nums[0];
        for(int i=3;i<n;++i){
            dp[i] = max(dp[i-1],dp[i-2] + nums[i-1]);
        }
        answer_a = dp[n-1];
        dp[0] = dp[1] = 0;
        dp[2] = nums[1];
        for(int i=3;i<=n;++i){
            dp[i] = max(dp[i-1],dp[i-2] + nums[i-1]);
        }
        return max(answer_a,dp[n]);
    }
};

分析：分两种情况进行讨论，选第一个和不选第一个。

错误：看了一下思路，最后调通了

Leetcode 53

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n+1);
        dp[0] = -20000;
        for(int i=1;i<=n;++i){
            dp[i] = max(nums[i-1],dp[i-1] + nums[i-1]);
        }
        return *max_element(dp.begin(),dp.end());
    }
};

分析：dp数组记录以当前位置为结尾的子数组的最大和，因此后面再加一位有两种可能，一是和这个一起，二是自己一组。最后取最大的部分即可。

错误：开始没想太懂，后来自己调通了。

Leetcode 343

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

class Solution {
public:
    int integerBreak(int n) {
        vector<int> dp(n+1);
        for(int i=2;i<=n;++i){
            for(int j=1;j<i;++j){
                dp[i] = max(dp[i],max(j*(i-j),j*dp[i-j]));
            }
        }
        return dp[n];
    }
};

分析：对于正整数n，当n≥2时，可以拆分成至少两个正整数的和。令x是拆分出的第一个正整数，则剩下的部分是n-x，n−x可以不继续拆分，或者继续拆分成至少两个正整数的和。每个正整数对应的最大乘积取决于比它小的正整数对应的最大乘积。

错误：分割问题还是没有什么思路

Leetcode 583

给定两个单词 word1 和 word2 ，返回使得 word1 和 word2 相同所需的 最小步数 。每步可以删除任意一个字符串中的一个字符。

class Solution {
public:
    int minDistance(string word1, string word2) {
        int m = word1.size();
        int n = word2.size();
        vector<vector<int>> dp(m+1,vector<int>(n+1,0));
        for(int i=0;i<=m;++i){
            dp[i][0] = i;
        }
        for(int i=0;i<=n;++i){
            dp[0][i] = i;
        }
        for(int i=1;i<=m;++i){
            for(int j=1;j<=n;++j){
                if(word1[i-1] == word2[j-1]){
                    dp[i][j] = dp[i-1][j-1];
                }
                else{
                    dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + 1;
                }
            }
        }
        return dp[m][n];
    }
};

分析：不相等的时候看两边的字符串，相等的时候看前一位

错误：字符相等的时候有些没想明白，后来调通了

Leetcode 646

给出 n 个数对。 在每一个数对中，第一个数字总是比第二个数字小。现在，我们定义一种跟随关系，当且仅当 b < c 时，数对 (c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

class Solution {
public:
    static bool cmp(vector<int> &a,vector<int> &b){
        return a[0] < b[0];
    }
    int findLongestChain(vector<vector<int>>& pairs) {
        int n = pairs.size();
        sort(pairs.begin(),pairs.end(),cmp);
        vector<int> dp(n+1,1);
        for(int i=1;i<=n;++i){
            for(int j=0;j<i-1;++j){
                if(pairs[i-1][0] > pairs[j][1]){
                    dp[i] = max(dp[i],dp[j+1]+1);
                }
            }
        }
        return dp[n];
    }
};

分析：排序后进行动态规划即可

错误：排序有问题。

Leetcode 376

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。给你一个整数数组 nums ，返回 nums 中作为摆动序列的最长子序列的长度 。

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        if(n == 1 || (n == 2 && nums[0] != nums[1])){
            return n;
        }
        if(n == 2 && nums[0] == nums[1]){
            return 1;
        }
        vector<int> up(n),down(n);
        up[0] = down[0] = 1;
        for(int i=1;i<n;++i){
            if(nums[i] > nums[i-1]){
                up[i] = max(up[i-1],down[i-1] + 1);
                down[i] = down[i-1];
            }
            else if(nums[i] < nums[i-1]){
                up[i] = up[i-1];
                down[i] = max(down[i-1],up[i-1] + 1);
            }
            else{
                up[i] = up[i-1];
                down[i] = down[i-1];
            }
        }
        return max(up[n-1],down[n-1]);
    }
};

分析：每当我们选择一个元素作为摆动序列的一部分时，这个元素要么是上升的，要么是下降的，这取决于前一个元素的大小。那么列出状态表达式为：up[i]表示以前 i个元素中的某一个为结尾的最长的「上升摆动序列」的长度。down[i]表示以前i个元素中的某一个为结尾的最长的「下降摆动序列」的长度。

错误：没有思路

Leetcode 494

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (int& num : nums) {
            sum += num;
        }
        int diff = sum - target;
        if (diff < 0 || diff % 2 != 0) {
            return 0;
        }
        int n = nums.size(), neg = diff / 2;
        vector<vector<int>> dp(n + 1, vector<int>(neg + 1));
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            int num = nums[i - 1];
            for (int j = 0; j <= neg; j++) {
                dp[i][j] = dp[i - 1][j];
                if (j >= num) {
                    dp[i][j] += dp[i - 1][j - num];
                }
            }
        }
        return dp[n][neg];
    }
};

分析：转化为0-1背包问题

错误：背包问题一直都不怎么理解，就先这样，后续再补充。

Leetcode 714

给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。

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

分析：股票问题的变形，比较类似于状态机，不是很能想得到

错误：股票问题后面也要再做一做

总结

动态规划比较有难度，一是状态转移方程的写法，二是在实现状态转移中的各种细节。以后对于动态规划还要勤加练习，多练习思考方法。