动态规划作为算法中较难的部分，还是下定决心慢慢整理。人生建议：遇到太难的动态规划，建议直接放弃。动态规划解题也有技巧，一般而言题目的问题都是：移动最少的次数到达终点。此时我们只需要：

设置 dp 数组，数组大小一般和输入相同，但细节需要微操。dp[i] 的含义是，到达 i 的最少次数
对 dp 数组进行初始化，即开始动态规划时，起始所需的次数，一般为 0，不过也有特殊情况
dp 的转移，如何从上一状态计算当前状态

掌握这三点，一般难度的动态规划是可以做出来的。

一维状态转移

45. 跳跃游戏 II

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是使用最少的跳跃次数到达数组的最后一个位置。假设你总是可以到达数组的最后一个位置。

输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

一维的状态转移是较为简单的动态规划。直接动态规划三步走，我们设 dp[i] 表示到达数组第 i 个位置需要的最少次数。第 i 个位置最小次数这个状态 dp[i]，有两种方式得到，要么本身最小，要么由上一个状态 +1 的来，即：dp[i] = min(dp[i], dp[i-1] +1)。

因此，我们的初始值要为 INT_MAX，因为如果用 0 初始化，dp[i] 始终为 0。我们写出程序：

class Solution {
public:
    int jump(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i < nums.size(); i++) {
            // 从 i 开始，能跳到的位置
            for (int j = 1; j <= nums[i]; j++) {
                // 这些位置的状态
                if (i + j < n) {
                    dp[i + j] = min(dp[i + j], dp[i] + 1);
                }
            }
        }
        return dp[n-1];
    }
};

通过这一题，顺便补充一点：动态规划中，$O(n^2)$ 时间复杂度的程序比较常见，不必担心超时。

多维动态规划

股票买卖问题是简单的多维动态规划问题，一维动态规划是：dp[i] 表示第 i 步的最优结果，多维动态规划 dp[i][j] 是指第 i 步的第 j 个选择下的最优结果。也就是，多维动态规划会有多种选择情况，注意这里的选择不是状态转移时的选择。而对于股票买卖问题有两种选择，买入或卖出。从简到难来学习下股票买卖问题：

121 买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。示例：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

动态规划三部曲：

dp[i]的含义：我们设 dp[i][0] 表示不持有股票的最大利润，dp[i][1] 表示持有股票时获得的最大利润
初始化：根据如上的定义，dp[0][0] 表示在最开始没有买入，因此利润为0；dp[0][1] 表示最开始就买入，此时利润为 -prices[0]
状态转移：dp[i][0] 有两种状态来源，要么保持不持有的状态，要么从上一个持有状态卖出。dp[i][1] 同理，要么保持上一个持有状态，要么从不持有股票变成持有股票。

而最大收益是，在最后时刻卖出了股票。如上所述，我们写出程序：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));
        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]);
            dp[i][1] = max(dp[i-1][1], -prices[i]);
        }
        return dp[n-1][0];
    }
};

122. 买卖股票的最佳时机 II

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。返回你能获得的最大利润。示例：

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
     总利润为 4 + 3 = 7 。

和上一题不一样的是，这个题可以多次买卖股票，那么动态规划的三部曲哪里不一样了呢？dp[i] 的定义和初始化肯定不会变，那么唯一不同的就是状态转移。

对于不持有股票，要么继续不持有，要么此刻卖出
对于持有股票，要么继续不持有，要么买入。但是这里的买入和上一题的是不一样的，上一题的买入是 -prices[i]，也就是本金为 0 的情况下买入；而这个题允许多次买卖，因此买入的时候应该是 dp[i-1][0]-prices[i]，本金为 dp[i-1][0]，也就是买入的股票全部卖出时的收益。

如上所述，简单的修改程序：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));
        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]);
            // 有了本金
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]);
        }
        return dp[n-1][0];
    }
};

714. 买卖股票的最佳时机含手续费

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

输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:  
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8

如上，能推断出是状态转移发生的变化。而且是卖出即不持有股票时需要减去手续费，同理，直接写出程序：

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));
        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];
    }
};

309. 最佳买卖股票时机含冷冻期

给定一个整数数组 prices，其中第 prices[i] 表示第 i 天的股票价格。设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。示例:

1
2
3

输入: prices = [1,2,3,0,2]
输出: 3 
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

这次的限制是有冻结时限，对应到转移方程，就是在买入的时候，应该用前天的不持有股票的状态作为本金，不能用昨天的。也就是，买入的 dp[i-1][0] - prices[i] 改为 dp[i-2][0] - prices[i]，处理一下越界的情况即可。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(2, 0));
        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]);
            if (i == 1)
            // 越界，要么保留上一个持有股票的状态，要么这一时刻买入
                dp[i][1] = max(dp[i-1][1], -prices[i]);
            else
                dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i]);
        }
        return dp[n-1][0];
    }
};

123. 买卖股票的最佳时机 III

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。示例:

输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
     随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

这个题和前面不同的是，开始限制了交易次数。也就是说，我们需要在增加一个状态，来表示第 k 次交易所能获得的最大利润。还是动态规划三部曲：

dp[i][k][0] 表示在第 i 天，交易了 k 次，不持有股票的最大收益；dp[i][k][1] 表示在第 i 天，交易了 k 次，持有股票的最大收益
对于初始化，dp[0][j][0] 表示在最开始，无论几次交易都不持有股票，收益为 0；dp[0][j][1] 表示在最开始，不管进行了几次交易，手上持有股票，那么收益为 -prices[0]，因为只能买入第一天的股票。
在状态转移时，如果是不持有股票，那么最大收益可能是继续不持有，或者上一持有状态卖出；而持有股票，如果是最开始交易，那么保留上一时刻的买入状态或重新买入，或者此刻买入。如果不是首次交易，买入的时候，用之间的收益减去买入价格，就是此刻的收益。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int k = 2;
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(k, vector<int>(2, 0)));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < k; j++) {
                // base case
                if (i == 0) {
                    dp[0][j][0] = 0;
                    dp[0][j][1] = -prices[0];
                } else {
                    // 第 j 次交易不持有，要么继续不持有，要么卖出
                    // 持有到卖出是一次交易，因此 j 不用变
                    dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
                    // 持有时，要么保留持有状态，要么在上一次的交易上继续买入
                    if (j == 0)
                        dp[i][j][1] = max(dp[i-1][j][1], -prices[i]);
                    else
                        dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
                }
            }
        }
        return dp[n-1][k-1][0];
    }
};

188. 买卖股票的最佳时机 IV

给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。示例：

1
2
3

输入：k = 2, prices = [2,4,1]
输出：2
解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。

和上一题一样了。

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

打家劫舍问题

198. 打家劫舍

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

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

这个是单状态的状态转移，当前状态有两种选择，要么偷当前屋子，要么偷上上个屋子，进行转移即可
因此初始化状态就是 dp[0]=nums[0], dp[1]=max(dp[0], nums[1])

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

213. 打家劫舍 II

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

1
2
3

输入：nums = [2,3,2]
输出：3
解释：你不能先偷窃 1 号房屋（金额 = 2），然后偷窃 3 号房屋（金额 = 2）, 因为他们是相邻的。

和上一题一样，既然是首尾相连的村庄，也就是首尾不能同时抢
既然如此，我们划分数组，第一个数组是 nums[0,,,n-1]，第二个数组是 nums[1,,,n]，计算这两个数组的最大值，选择其中最大的即可

class Solution {
public:

    int maxRob(vector<int>& t1) {
        int n = t1.size();
        vector<int> dp(n, 0);
        dp[0] = t1[0];
        dp[1] = max(t1[0], t1[1]);

        for (int i = 2; i < n; i++) {
            dp[i] = max(dp[i-2] + t1[i], dp[i-1]);
        }
        return dp.back();
    }

    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> t1{nums.begin(), nums.end() - 1};
        vector<int> t2{nums.begin() + 1, nums.end()};

        return max(maxRob(t1), maxRob(t2));
    }
};

337. 打家劫舍 III

小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root。除了 root 之外，每栋房子有且只有一个「父」房子与之相连。一番侦察之后，聪明的小偷意识到这个地方的所有房屋的排列类似于一棵二叉树。如果两个直接相连的房子在同一天晚上被打劫，房屋将自动报警。给定二叉树的 root 。返回在不触动警报的情况下，小偷能够盗取的最高金额。

1
2
3

输入: root = [3,2,3,null,3,null,1]
输出: 7 
解释: 小偷一晚能够盗取的最高金额 3 + 3 + 1 = 7

这个某种程度上算是二叉树的后续遍历问题。

对于某个节点，当前的最大抢劫收益是：要么抢当前节点，此时就不能抢孩子节点；要么抢孩子节点；要么不抢孩子节点，也不抢当抢节点
我们可以看到，节点的状态取决于孩子节点，这样，我们能得到两个信息，第一个信息是需要给每个孩子节点返回状态，状态就是：当前节点的最大抢劫收益，第二个信息是需要先有孩子节点的状态，才能确定当前节点的状态，因此需要后续遍历
定义一个状态，表示抢或不抢所带来的最大收益，如果遍历期间越界，那么收益就是 0，按照前面说的三种状态进行转移即可

struct node {
    int s;
    int n;
};

class Solution {
public:

    node maxrob(TreeNode* root) {
        if (root == nullptr)
            return {0, 0};
        auto a = maxrob(root->left);
        auto b = maxrob(root->right);
        // 抢当前节点
        int s = root->val + a.n + b.n;
        // 叶子节点的抢或不抢选最大值
        int n = max(a.s, a.n) + max(b.s, b.n);
        // 三种状态选最大值
        return {s, n};
    }

    int rob(TreeNode* root) {
        auto a = maxrob(root);
        // 抢或不抢选最大值
        return max(a.s, a.n);
    }
};

子序列问题

300. 最长递增子序列

给你一个整数数组 nums，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。示例：

1
2
3

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

子序列与子串不同，子序列的元素之间可以不连续，子串的元素之间必须连续。在了解基本问题后，我们进行动态规划：

设 dp[i] 表示第 i 个位置处的最长递增子序列长度。且递增子序列，取决于两个字符的大小关系
因此要计算 dp[i]，就必须要知道 i-1 处的最大长度，以及 nums[i-1] 和 nums[i] 的大小关系
因此我们需要 $O(n^2)$ 的算法，j 指针指向的位置小于 i 指针，判断 nums[j] 和 nums[i] 的大小关系，并得到 dp[i] 的值

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

354. 俄罗斯套娃信封问题

给你一个二维整数数组 envelopes，其中 envelopes[i] = [wi, hi]，表示第 i 个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。请计算最多能有多少个信封能组成一组俄罗斯套娃信封（即可以把一个信封放到另一个信封里面）。注意：不允许旋转信封。示例：

1
2
3

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

这个问题很有趣，也算是一种最长递增子序列问题。只不过需要预先的排序处理：

首先按照宽度进行升序排列
对于宽度相同的信封，按照高度进行降序排列
针对高度，求得的最长递增子序列，就是能套娃的最大数量。因为宽度已经默认升序，而高度的最长递增子序列也是升序，即信封的最大数量

class Solution {
public:

    static bool cmp(vector<int>& a, vector<int>& b) {
        if (a[0] != b[0])
            return a[0] < b[0];
        return a[1] > b[1];
    }

    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(), envelopes.end(), cmp);
        int n = envelopes.size();
        vector<int> dp(n, 1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (envelopes[i][1] > envelopes[j][1]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }
        int maxn = -1;
        for (auto i : dp) {
            maxn = max(maxn, i);
        }
        return maxn;
    }
};

53. 最大子数组和

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

1
2
3

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

动态规划三部曲：

设 dp[i] 表示数组的第 i 个位置处，最大的子数组和
初始化：dp[0]=nums[0]
状态转移：dp[i] 要么来自上一个子数组，要么是当前数组元素重新开始，dp[i]=max(dp[i-1]+nums[i], nums[i])

但是有一个细节需要注意，在遍历 dp 求最大值的时候，如果我们此时不知道最小值是多少，就用 dp[0] 作为最小值，不然的话容易计算错误。比如数组是 [-3,-4,-5]，我们用 -1 作为最小值去选择最大值是错误的。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n, 0);
        dp[0] = nums[0];
        for (int i = 1; i < n; i++) {
            dp[i] = max(dp[i-1] + nums[i], nums[i]);
        }
        // 注意
        int maxn = dp[0];
        for (int i : dp) {
            maxn = max(maxn, i);
        }
        return maxn;
    }
};

1143. 最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0。一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，ace 是 abcde 的子序列，但 aec 不是 abcde 的子序列。两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

1
2
3

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

对于这种基于两个输入求解一个输出，通常要涉及二维的动态规划：

dp[i][j] 表示 text1[0,...,i] 和 text2[0,...,j] 的最长公共子串的长度
那么进行初始化，最开始的时候，默认不存在最长公共子串，因此 dp 数组的取值都是 0。dp[0][j] 表示 text1[0] 和 text2 的最长公共子串的长度，因此只要 text1[0]==text2[j]，那么 dp[0][j,...,n] 这些取值都为 1。同理可以得到 dp[i][0] 的值
开始状态转移，这里需要注意的是，无论 text1[i] 是否与 text2[j] 相等，都需要计算 dp[i][j]，假如 asdf 和 asdg，在 f,g 处，最长的公共子串仍然是 3。
而 dp[i][j] 的状态有 3 种选择，text1[i]==text[j]，此时 dp[i][j]=dp[i-1][j-1]+1；否则就在 dp[i-1][j] 和 dp[i][j-1] 这两者之间选择一个最大值即可。

class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size(), n = text2.size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        for (int i = 0; i < n; i++) {
            if (text1[0] == text2[i]) {
                for (int j = i; j < n; j++) {
                    dp[0][j] = 1;
                }
                break;
            }
        }
        for (int i = 0; i < m; i++) {
            if (text2[0] == text1[i]) {
                for (int j = i; j < m; j++)
                    dp[j][0] = 1;
                break;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                // 注意
                int a = text1[i] == text2[j] ? dp[i-1][j-1] + 1 : dp[i-1][j-1];
                int b = max(dp[i-1][j], dp[i][j-1]);
                dp[i][j] = max(a, b);
            }
        }
        return dp[m-1][n-1];
    }
};

72. 编辑距离

给你两个单词 word1 和 word2，请返回将 word1 转换成 word2 所使用的最少操作数。你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

当时看到这个题目的时候，我是晕晕的不知如何解决，直到看了答案，还是动态规划三步走吧：

前面我们知道，对于这种求两种字符串的状态，需要设置 dp[i][j]，表示从 word1[i] 到 word2[j] 的最小编辑距离
初始化：再明确 dp[i][j] 的定义后，需要进行简单的初始化。如下所示，当 word1[0] == word2[i] 时，我们只需要保留相同的元素，插入其他元素即可，此时可以少修改一个。否则，修改的次数就是 word2 的长度，分别是替换与插入。

bool flag = false;
for (int i = 0; i < n; i++) {
    if (word1[0] == word2[i]) {
        dp[0][i] = i;
        flag = true;
    } else {
        if (flag)
            dp[0][i] = i;
        else
            dp[0][i] = i + 1;
    }
}

状态转移。如果 word1[i]==word2[j]，说明此时不用进行任何操作，那么 dp[i][j] 所代表的次数就和 dp[i-1][j-1] 相同。如果 word1[i] != word2[j]，就说明此时要么进行插入，要么进行删除，要么进行替换，在三者中选择一个最小的代价。这里我们需要注意的是：对于任何 dp[i][j]，都是以 dp[i-1][j-1] 为基础出发的。

dp[i][j-1] 为 word1 的前 i 个字符和 word2 的前 j - 1 个字符编辑距离的子问题。即在 dp[i-1][j-1] 的基础上 i 增加了，表示我们需要在 word1 的末尾添加了一个相同的字符，那么 dp[i][j] 最小可以为 dp[i][j-1] + 1；

dp[i-1][j] 为 word1 的前 i - 1 个字符和 word2 的前 j 个字符编辑距离的子问题。即在 dp[i-1][j-1] 的基础上 j 增加了，表示我们删除 word1 末尾的字符，那么 dp[i][j] 最小可以为 dp[i-1][j] + 1；

dp[i-1][j-1] 为 word1 前 i - 1 个字符和 word2 的前 j - 1 个字符编辑距离的子问题。即对于 word2 的第 j 个字符，我们修改 word1 的第 i 个字符使它们相同，那么 dp[i][j] 最小可以为 dp[i-1][j-1] + 1。特别地，如果 word1 的第 i 个字符和 word2 的第 j 个字符原本就相同，那么我们实际上不需要进行修改操作。在这种情况下，dp[i][j] 最小可以为 dp[i-1][j-1]。

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

背包问题

416. 分割等和子集

给你一个只包含正整数的非空数组 nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。示例：

1
2
3

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

假设数组的总和是 2sum，那么一半就是 sum。这是一个背包问题，意思是现在有 nums 个物品，每个物品的重量是 nums[i]，能不能将 nums 中的若干个物品装入一个背包，使背包内物品的重量为 sum。由于 nums[i] 只能使用一次，因此这是一个 0-1 背包问题。

我们设 dp[i][j] 表示使用前 i 个物品，装入质量为 j 的背包能否装下。这也是一般背包问题的 dp 数组创建方法。因此最后我们只需要判断 dp[n-1][sum] 即可。
初始化：背包可以选择不装入任何物体，因此 dp[0,...,n][0] 的取值为 1，表示有 1 中方法使得背包中物体的重量是 0，即什么都不装。
状态转移：对于物品 nums[i]，如果当前背包所允许的重量小于 nums[i]，就说明当前物体不能放进来，因此 dp[i][j] 就等于 dp[i-1][j]，表示当前能装下的重量等于：同等背包的大小下，少装一个物体的状态，继承之前的结果。
否则，dp[i][j] 就等于 dp[i-1][j] 和 dp[i-1][j - nums[i]] 的最大值，选择一个最大值表示装或者不装，前者表示不装当前物体，后者表示装当前物体，既然要装当前物体，就需要腾出一些空间来，而腾出的空间是 j-nums[i]。在这个限制下，也就是能保证装入新物体的前提下，腾出来的空间最少，这样可以装的物体最多。

还有一些细节需要注意，因为背包问题需要访问到 sum，因此创建 dp 数组时需要 sum 个元素，也就是需要 +1。至于为什么都是 dp[i-1]，因为装 nums[i] 之前，nums[i] 还没进入背包，因此只能使用装了前 i-1 个物品的背包。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (auto i : nums)
            sum += i;
        if (sum % 2 != 0)
            return false;
        sum /= 2;
        int n = nums.size();
        vector<vector<int>> dp(n + 1, vector<int>(sum + 1, 0));
        // 不装物品，方案为 1
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= sum; j++) {
                // 装不下，就选择不装
                if (j < nums[i - 1]) {
                    dp[i][j] = dp[i-1][j];
                }
                // 装得下，选择装和不装的最大状态
                else {
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j - nums[i-1]]);
                }
            }
        }
        return dp[n][sum];
    }
};

518. 零钱兑换 II

给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。假设每一种面额的硬币有无限个。示例：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

当一个物品不被限制次数选择时，就说明这是一个完全背包问题。对于 0-1 背包问题，取值是两者取最大，表示只能选择一个；对于完全背包问题，取值是两者之和，表示两种选择我都要。剩下的和 0-1 背包完全一致了：

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1, 0));
        for (int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= amount; j++) {
                if (j < coins[i-1]) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    // 我全都选
                    dp[i][j] = dp[i-1][j] + dp[i][j - coins[i-1]];
                }
            }
        }
        return dp[n][amount];
    }
};

再来说两个细节吧。

状态转移的时候，i 和 j 都是从 1 开始的。对于 i 遍历的所有物品，0 表示没有物品，因此没必要进行转移，状态就是初始设置的 0。对于 j 遍历的所有背包，0 同样表示不选择物品，初始化状态已经预设且始终为 1。
对于选最大值的情景，0-1 背包问题的转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j - nums[i-1]]);，完全背包问题的转移方程：dp[i][j] = max(dp[i-1][j], dp[i][j - nums[i-1]]);。区别在于：dp[i-1][j - nums[i-1]] 和 dp[i][j - nums[i-1]]。可以这么理解，对于 0-1 背包问题，一个物品只能选一次，因此在选第 i 个物品时，上一个选择的物品只能是第 i-1 个；对于完全背包问题，一个物品可以选很多次，因此在选择第 i 个物品时，上一个选择的物品仍然能是第 i 个。

Just for Life.

算法系列：动态规划