动态规划

递归与动态规划导论

509-斐波那契数

斐波那契数列 [0, 1, 1, 2, 3, 5, 8, ...] 可以表示为递归形式：

int fib(n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n-1) + fib(n-2);
}

涉及递归的问题都可以画出递归树，对于分析算法复杂度、寻找算法低效的原因、找到高效的解法有很大帮助！假设求 fib(20)，画出递归树后会发现，这个递归存在着大量重复计算，假设 N = 20，那么树的高度是 20，树的节点数是 2 ^ N，算法复杂度是 O(2^n)，这太大了！

因此我们可以用一个数组或者哈希表存储已经计算过的结果，当遍历递归树遇到同样的节点时，就可以快速访问到结果而不必重复计算，这就是“剪枝”。通过剪枝，把一颗存在巨量冗余的递归树，变成了不存在冗余的递归图，fib(20) ... fib(1) 每个结果都只计算了一次。这就是“记忆化递归”！

递归的思路是把一个大问题，自顶向下分解成子问题，最后到达递归树的叶子结点，然后逐层返回计算结果。而动态规划的思想，是从最小子问题开始，即 f(1) 和 f(2)，自底向上，逐步构建出大问题的解。

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

322-零钱兑换

给定不同面额的硬币和一个目标金额，计算可以凑成目标金额的最少硬币个数；如果不能凑成目标金额，返回  -1。每一种硬币的数量不限。

递归方案，自顶向下思考。由于每一种硬币的数量不限，每一步都可以选择任意一枚硬币，这是一个 N 叉递归树的前序遍历。

举例：目标 11 元，硬币 [1, 2, 5]。最少硬币数 dfs(11) = 1 + min(dfs(11-1), dfs(11-2), dfs(11-5))

这个递归调用存在许多子问题被重复计算，因此我们需要一个缓存，来实现递归树的剪枝。

class Solution {
public:
    int dfs(vector<int> &coins, int target, unordered_map<int, int> &um) {
        if (target < 0) return -1;
        if (target == 0) return 0;
        if (um.find(target) != um.end()) {
            return um[target];
        }
        int res = INT_MAX;
        for (int c : coins) {
            int cur = 1 + dfs(coins, target - c, um);
            if (cur > 0)
                res = min(res, cur);
        }
        um[target] = res == INT_MAX ? -1 : res;
        return um[target];
    }

    int coinChange(vector<int>& coins, int amount) {
        unordered_map<int, int> um;
        return dfs(coins, amount, um);
    }
};

动态规划问题的两个要素：最优子结构、状态转移方程。

• 最优子结构：问题的最优解，可以从其子问题的最优解构造出来。
• 状态转移方程：假设已知子问题的最优解 dp[0] ... dp[n-1]，如何得到问题的最优解 dp[n]。

如何找到最优子结构？——“问什么就设什么”。这道题目问的是凑成总金额 S 所需的最少的硬币个数。我们就设 F(S) 为组成金额 S 最少的硬币数。

画 N * M 表格。N = len(coins) + 1，M = amount + 1。

第一行，什么硬币也不选。代表 dp 数组的初始状态。其中 dp[0] = 0，0 元不需要硬币。

第二行，选择 2 元硬币。对于 amount >= 2，dp[i] = (1 + dp[i-2]) if dp[i-2] != -1 else -1

第三行，选择 5 元硬币，对于 amount >= 5，要组合成 amount，可以用 1 + dp[i-5] 枚硬币，或者 dp[i] 枚硬币（继承上一行），结果应该是两者中较小的一个。得到状态转移方程 dp[i] = min(dp[i], 1 + dp[i-c])

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

518-零钱兑换 II

给定不同面额的硬币和一个目标金额，计算可以凑成目标金额的硬币组合数；如果不能凑成目标金额，返回 0。每一种硬币的数量不限。

这是一个典型的组合问题，对于每种硬币都有选与不选两种情况，且最后组成的金额可以拆分为更小的金额。这种大问题里嵌套子问题的，首先想到用动态规划解决。动态规划两步走——最优子结构（求什么就设什么）、状态转移方程（画表格）。

动态规划的过程就是一个填表格的过程，假设可用硬币为 [2, 5, 10]，计算 amount = 11 元的组合总数，M = len([2, 5, 10])，N = 11，画一个 M+1 行，N+1 列的表格。

填第一行，即什么硬币都不选。

填第二行，此时选择了硬币 [2]，对于 amount < 2，用 2 元硬币无法凑成，因此结果是直接继承上一行。对于 amount >= 2，则组合数 = 选择 2 元硬币的组合数 + 不选择 2 元硬币的组合数。

其中，不选择 2 元硬币的组合数 = dp[i]，继承上一行。选择 2 元硬币的组合数 = dp[i-2]。这是动态规划中重要的思想——前面计算的结果可以为后面所用。由于我们是从左往右遍历，我们已经计算出了 dp[i-2] 的组合数，dp[i] 的每种组合即 dp[i-2] 的每种组合加上一枚 2 元硬币。

因此我们得到了一个递推关系：dp[i] = dp[i] + dp[i-coin]

而且，在动态计算的过程中，dp[i] 的计算只与上一行有关，因此我们只需要一个长度为 amount+1 的数组作为存储即可。

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

背包问题

背包问题

给定不同大小的物品和一个背包，每个物品的大小为 A[i]，背包容量为 m，挑选物品装入背包，问最大能装多满？

动态规划，物品一个一个选，背包容量一点点增大。填表格时，因为每件物品只能选择一次，所以每一行要从右往左填，不能让左边填好的结果影响右边；填每一个格子时，可能上一行的结果更好，所以取的是 max(dp[i], a + dp[i-a])。

class Solution {
public:
    int backPack(int m, vector<int> &A) {
        vector<int> dp(m+1, 0);
        for (int a : A) {
            for (int i = m; i >= a; --i) {
                dp[i] = max(dp[i], dp[i-a] + a);
            }
        }
        return dp[m];
    }
};

背包问题 II

给定不同大小的物品和一个背包，每个物品的大小为 A[i]、价值为 V[i]，背包容量为 m，挑选物品装入背包，问能装入背包的最大价值是多少？

class Solution {
public:
    int backPackII(int m, vector<int> &A, vector<int> &V) {
        vector<int> dp(m + 1, 0);
        for (int i = 0; i < A.size(); ++i) {
            for (int j = m; j >= A[i]; --j) {
                dp[j] = max(dp[j], dp[j-A[i]] + V[i]);
            }
        }
        return dp[m];
    }
};

背包问题 III

给定不同大小的物品和一个背包，每个物品的大小为 A[i]、价值为 V[i]，背包容量为 m，挑选物品装入背包，每个物品可以选择不限次数，问能装入背包的最大价值是多少？

class Solution {
public:
    int backPackIII(vector<int> &A, vector<int> &V, int m) {
        vector<int> dp(m + 1, 0);
        for (int i = 0; i < A.size(); ++i) {
            for (int j = A[i]; j <= m; ++j) {
                dp[j] = max(dp[j], dp[j-A[i]] + V[i]);
            }
        }
        return dp[m];
    }
};

背包问题 IV

给定不同大小的物品和一个背包，每个物品的大小为 nums[i]，背包容量为 target，求能填满背包的方案数。每一个物品可以用无限次。

class Solution {
public:
    int backPackIV(vector<int> &nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for (int num : nums) {
            for (int i = num; i <= target; ++i) {
                dp[i] += dp[i-num];
            }
        }
        return dp[target];
    }
};

背包问题 V

给定不同大小的物品和一个背包，每个物品的大小为 nums[i]，背包容量为 target，求能填满背包的方案数。每一个物品只能用一次。

class Solution {
public:
    int backPackV(vector<int> &nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for (int num : nums) {
            for (int i = target; i >= num; --i) {
                dp[i] += dp[i-num];
            }
        }
        return dp[target];
    }
};

背包问题 IX

你总共有 n 万元，希望申请国外的大学，给出每个大学的申请费用、以及得到 offer 的概率。可以同时申请多所大学。找到至少获得一份 offer 的最大概率。

获得至少一份 offer 的概率 = 1 - 没有 offer 的概率。设 dp[i] 为花 i 元申请大学，没有 offer 的概率。

class Solution {
public:
    double backpackIX(int n, vector<int> &prices, vector<double> &probability) {
        vector<double> dp(n+1, 1.0);
        for (int i = 0; i < prices.size(); ++i) {
            for (int j = n; j >= prices[i]; --j) {
                double noOffer1 = dp[j-prices[i]];
                double noOffer2 = 1 - probability[i];
                double noOffer = noOffer1 * noOffer2;
                dp[j] = min(dp[j], noOffer);
            }
        }
        return 1 - dp[n];
    }
};

动态规划

10-正则表达式

算法的设计是一个螺旋上升、逐步完善的过程，正则表达式匹配就是一个典型的例子。

先不考虑正则表达式，我们先看一个递归形式的字符串匹配，这个算法充分体现了递归的思想——递归函数返回的结果，被当下执行的函数所利用。或者说，管好当下，后面的交给递归去解决。

def isMatch(s, p):
    if len(p) == 0: return len(s) == 0
    firstMatched = len(s) != 0 and p[0] == s[0]
    return firstMatched and isMatch(s[1:], p[1:]) ## 第一个字符相同，剩下的字符串同理。

然后我们处理 . 通配符（可以代表任何单个字符）：

def isMatch(s, p):
    if len(p) == 0: return len(s) == 0
    ## 提示：一个短的正则表达式可以匹配很长的字符串，所以这里我们是检查 p[0] 是否在某些字符范围里
    firstMatched = len(s) != 0 and p[0] in {s[0], '.'}
    return firstMatched and isMatch(s[1:], p[1:])

然后我们处理 * 通配符：

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if len(p) == 0: return len(s) == 0
        firstMatched = len(s) != 0 and p[0] in {s[0], '.'}
        if len(p) >= 2 and p[1] == '*':
            ## 当前发现 * 通配符
            ## p[0] 匹配零次：self.isMatch(s, p[2:])
            ## p[0] 匹配第一个字符：firstMatched and self.isMatch(s[1:], p)
            return self.isMatch(s, p[2:]) or (firstMatched and self.isMatch(s[1:], p))
        else:
            return firstMatched and self.isMatch(s[1:], p[1:])

显然这个递归存在大量重复计算，用记忆化递归改造：

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        cache = {}
        return self.match(s, p, 0, 0, cache)

    def match(self, s, p, i, j, cache):
        if j >= len(p): return i >= len(s)
        if (i, j) in cache:
            return cache[(i, j)]
        firstMatched = i < len(s) != 0 and p[j] in {s[i], '.'}
        if j < len(p) - 1 and p[j+1] == '*':
            cache[(i, j)] = self.match(s, p, i, j+2, cache) or (firstMatched and self.match(s, p, i+1, j, cache))
            return cache[(i, j)]
        else:
            cache[(i, j)] = firstMatched and self.match(s, p, i+1, j+1, cache)
            return cache[(i, j)]

本题也可以用动态规划解决。

一、最优子结构：dp[i][j] 表示 s 的前 i 个是否能被 p 的前 j 个匹配

二、状态转移方程：已知 `dp[i-1][j-1]`、s[i]、p[j]，如何求 `dp[i][j]`？

当 p[j] in {s[i], '.'}，则 dp[i][j] = dp[i-1][j-1]

考虑 \* 通配符，\* 的含义是匹配前面的字符零次或多次

p[j] == '\*' and p[j-1] == s[i] or p[j-1] == "."，\* 前面的字符可以匹配 N 次，……

p[j] == '\*' and p[j-1] != s[i]，\* 前面的字符匹配不上，只能匹配零次，则 `dp[i][j] = dp[i][j-2]

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        M = len(s)
        N = len(p)
        dp = [[False for _ in range(N+1)] for _ in range(M+1)]
        ## 初始化
        dp[0][0] = True
        for j in range(1, N+1):
            if p[j-1] == '*':
                dp[0][j] = dp[0][j-2]
        ## 计算
        for i in range(1, M+1):
            for j in range(1, N+1):
                if p[j-1] in {s[i-1], '.'}:
                    dp[i][j] = dp[i-1][j-1]
                elif p[j-1] == '*':
                    if p[j-2] in {s[i-1], '.'}:
                        dp[i][j] = dp[i][j-2] or dp[i-1][j-2] or dp[i-1][j]
                    else:
                        dp[i][j] = dp[i][j-2]
        return dp[M][N]

53-最大和子数组

一、找最优子结构——问什么设什么，题目求的是最大和连续子数组的和，我们就设 dp[i] 为以 nums[i] 结尾的最大子数组和。

二、找状态转移方程——如果全是正数，那么最大和子数组就是 nums 全体。因为有负数的存在，而 dp[i] 是以 nums[i] 为结尾的，因此容易推出 dp[i] = nums[i] + (dp[i-1] if dp[i-1] > 0 else 0)

class Solution {
public:
    int maxSubArray(const vector<int> &nums) {
        if (nums.empty())
            return 0;
        int res = nums[0];
        int N = static_cast<int>(nums.size());
        vector<int> dp(N);
        dp[0] = nums[0];
        for (int i = 1; i < N; ++i) {
            dp[i] = nums[i] + (dp[i-1] > 0 ? dp[i-1] : 0);
            res = std::max(dp[i], res);
        }
        return res;
    }
};

62-不同路径

一个机器人位于一个 m x n 网格的左上角，每次只能向下或者向右移动一步。请问到达到网格的右下角总共有多少条不同的路径？

动态规划就是画表格，画表格就是动态规划。

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1 for i in range(n)] for i in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i][j-1] + dp[i-1][j]
        return dp[m-1][n-1]

63-不同路径 II

一个机器人位于一个 m x n 网格的左上角，每次只能向下或者向右移动一步。请问到达到网格的右下角总共有多少条不同的路径？网格中有障碍物。

dp[i][j] 表示到达网格 [i][j] 的路径总数，dp[i][j] = dp[i-1][j] + dp[i][j-1]，填表格时，由左往右、由上往下，dp[i][j] 的结果取决于左一格和上一格，dp 二维数组可以优化为一维，数组长度为列数。

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid)
        n = len(obstacleGrid[0])
        dp = [0 for i in range(n)]
        dp[0] = 1 if obstacleGrid[0][0] == 0 else 0
        for i in range(m):
            for j in range(n):
                if obstacleGrid[i][j] == 1:
                    dp[j] = 0
                    continue
                if j >= 1 and obstacleGrid[i][j-1] == 0:
                    dp[j] += dp[j-1]
        return dp[n-1]

64-最小路径和

一个机器人位于一个 m x n 网格的左上角，每个网格有一个非负整数，找出一条到右下角的路径，使得路径上的数字总和为最小。

72-编辑距离

给定两个字符串，找到使得 s1 转换为 s2 所需的最小步数，每步可以插入、删除、替换一个字符。

一、最优子结构——dp[i][j] 代表 word1[:i] 转换成 word2[:j] 需要的最少步数。

二、状态转移方程——

当 word1[i] == word2[j]，dp[i][j] = dp[i-1][j-1]；
当 word1[i] != word2[j]，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1。

第一行、第一列单独初始化：

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        M = len(word1)
        N = len(word2)
        dp = [[0 for _ in range(N+1)] for _ in range(M+1)]
        for i in range(1, M+1):
            dp[i][0] = i
        for j in range(1, N+1):
            dp[0][j] = j
        for i in range(1, M+1):
            for j in range(1, N+1):
                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], dp[i-1][j], dp[i][j-1]) + 1
        return dp[M][N]

91-解码

给定一个只包含数字的字符串，求解码方法的总数。（1 - A, 2 - B, ... 26 - Z）

一、最优子结构——设 dp[i] 为字符串 s[0...i] 的编码方法数。

二、状态转移方程。

• s[i] == '0'：如果与前一位组成 10 或 20，那么 dp[i] = dp[i-2]；否则无法解码（非法）。
• s[i] != '0'，如果与前一位组成 11 至 26 直接的数字，那么 dp[i] = dp[i-1] + dp[i-2]；否则 dp[i] = dp[i-1]。

class Solution {
public:
    int numDecodings(const string &s) {
        if (s[0] == '0')
            return 0;
        vector<int> dp(s.size());
        dp[0] = 1;
        for (int i = 1; i < s.size(); ++i) {
            if (s[i] == '0') {
                if ((s[i - 1] == '1' || s[i - 1] == '2')) {
                    dp[i] = i >= 2 ? dp[i - 2] : 1;
                } else {
                    return 0;
                }
            } else {
                if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] >= '1' && s[i] <= '6')) {
                    dp[i] = dp[i - 1] + (i >= 2 ? dp[i - 2] : 1);
                } else {
                    dp[i] = dp[i - 1];
                }
            }
        }
        return dp.back();
    }
};

139-单词拆分

这道题目起的是单词拆分，实际上还是一个组合问题。即给定一组单词和一个字符串，判断单词表里的单词能否组成字符串，每个单词可以使用无数次。

例如单词表 ["apple", "pen"]，字符串 "applepenapple"，返回 true。

最优子结构（求什么就设什么），设 dp[i] 为单词表能否组成 s[0:i]；

状态转移方程，每次转移的时候 s[i-1] 被包括进来，那么从 s[i-1] 向后遍历每一个位置 j，判断 s[j:i] 是否在单词表里；如果 s[0:j]、s[j:i] 都在单词表里，那么即满足条件！

// 伪代码表示
dp["leetcode"] = dp["leetcod"] && "e" in wordDict
...
dp["leetcode"] = dp["leet"] && "code" in wordDict

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        int N = static_cast<int>(s.size());
        vector<bool> dp(N + 1, false);
        dp[0] = true;
        unordered_set<string> us(wordDict.begin(), wordDict.end()); // vector 构造 unordered_set
        for (int i = 0; i <= N; ++i) {
            for (int j = i - 1; j >= 0; --j) {
                dp[i] = dp[j] && (us.find(s.substr(j, i-j)) != us.end());
                if (dp[i]) break;
            }
        }
        return dp[N];
    }
};

279-完全平方数

给定一个正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。求最少的完全平方数个数。

300-最长上升子序列

注意，子序列（subsequence）不一定是连续的；而子串、子数组（substring, subarray）是连续的。

一、找最优子结构——问什么就设什么，题目问的是找到最长上升子序列的长度，我们就设 dp[i] = 以 nums[i] 结尾的最⻓递增子序列的⻓度

二、找状态转移方程——dp[i] = max(d[0] ... d[i-1]) + 1

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

343-整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。求这个最大乘积。

最优子结构——设 dp[i] 为将 i 拆分后获得的最大乘积。

状态转移方程——当 i >= 2 时，可以至少拆分为两个正整数。令 j 是拆分出来的第一个整数，则剩下部分是 i - j，i - j 可以继续拆分，也可以不拆分，因此最大乘积是 max(j * (i-j), j * dp[i-j])。

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

376-摆动序列

给定一个整数数组，求最长摆动子序列的长度。摆动序列的定义：或者少于两个元素，或者相邻数字的差严格地在正数和负数之间交替。

413-等差数列

如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。给定一个整数数组，求数组中构成等差数列的子数组个数。（等差数列的 count >= 3）

设 dp[i] 为以 nums[i] 为结尾的等差子数组的个数。最终结果等于 dp[0] + dp[1] + ... + dp[N-1]。

每次转移，如果 nums[i] 与前两个数构成等差数列，那么 dp[i] = dp[i-1] + 1，这个 +1 意义是：

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        size_t N = nums.size();
        vector<int> dp(N);
        if (N <= 2) return 0;
        int res = 0;
        for (int i = 2; i < N; ++i) {
            if (nums[i] - nums[i-1] == nums[i-1] - nums[i-2]) {
                dp[i] = dp[i-1] + 1;
            } else {
                dp[i] = 0;
            }
            res += dp[i];
        }
        return res;
    }
};

416-分割等和子集

给定一个数组，是否可以将其分割成两个子集，使得两个子集的元素和相等。

首先，可以这样分割的前提是，这些数的总和是偶数。然后，题目转化为了经典的子集和问题（是否存在子集，元素和等于 sum 的一半）。

假设分割 [1,2,3,4] 这个集合，M = len(nums)，N = S/2，我们需要一个 M+1 行 N+1 列的表格。

填第一行，即什么都不选。

填第二行，此时选择了 [1]，对于 amount < 1，直接继承上一行。对于 amount >= 1，不选择 1 则 dp[i] = dp[i] 继承上一行，选择 1 则 dp[i] = dp[i-1]，因此 dp[i] = dp[i] or dp[i-1]。

特别地，因为此题中每个数字只能选择一次，因此在填写第二行时应该是从右往左填写，因为左边的结果是已经选择了 [1] 得到的，不能让左边的结果影响到右边。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int S = accumulate(nums.begin(), nums.end(), 0);
        if (S & 1) return false;
        S = S / 2;
        vector<bool> dp(S + 1, false);
        dp[0] = true;
        for (int num : nums) {
            for (int i = S; i >= num; --i) {
                dp[i] = dp[i] or dp[i-num];
            }
        }
        return dp[S];
    }
};

435-无重叠区间

给定一组区间，找到需要移除区间的最小数量，使剩余区间互不重叠。

首先分析题目，求最值，首先想到动态规划。动态规划就是求最值的，因为最值的产生肯定存在某种递推关系，前面计算的结果可以为后面所用。

然后，题目求的是需要移除区间的最小数量，就等同于求无重叠区间的最大个数。这个问题在生活中的应用广泛，比如你今天有好几个活动，每个活动都可以用区间 [start, end] 表示开始和结束的时间，显然你不能同时参加两个活动，请问你今天最多能参加几个活动呢？

然后，无重叠区间的特征是，在数轴上，后一个区间的起点不小于前一个区间的终点。这不就是上一道题——最长上升子序列吗？！我们需要先对区间们进行排序。

一、找最优子结构——问什么就设什么。设 dp[i] 为以第 i 个区间为结尾的最大不重叠区间个数。

二、找状态转移方程——求 dp[i] 时，前面任何一个区间都有可能与第 i 个区间重叠，我们需要找到 j < i 且 intervals[j] 与 intervals[i] 不发生重叠的所有 dp[j] 中的最大值。

有了动态规划思路后，写出代码，执行后发现非常耗时，原因是需要每次求 dp[i] 都需要遍历 dp[0...i]。

bool compare(const vector<int> &lhs, const vector<int> &rhs) {
    return lhs[1] < rhs[1];
}

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        std::sort(intervals.begin(), intervals.end(), compare);
        int N = intervals.size();
        if (N == 0) return 0;
        vector<int> dp(N, 1);
        int res = 1;
        for (int i = 1; i < N; ++i) {
            for (int j = i - 1; j >= 0; --j) { // 耗时的原因
                if (intervals[j][1] <= intervals[i][0]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            res = max(res, dp[i]);
        }
        return N - res;
    }
};

如何优化呢？在上面的解法中，dp[i] 代表包括第 i 个区间的解。这次，我们设 dp[i] 为“当前最优解”，它包括两种情况：

• intervals[i] 出现在无重叠区间里。我们可以在找到第一个不重叠的区间后停止遍历，因为这个区间的终点大于等于前面所有的终点！此时 dp[i] = dp[j] + 1，因为 dp[j] 存储了直到第 j 个区间的最优解！
• intervals[i] 不出现在无重叠区间里。此时 dp[i] 直接继承上一个最优解，dp[i] = dp[i-1]。

最终的 dp[i] 应该是两者中的较大值。

bool compare(const vector<int> &lhs, const vector<int> &rhs) {
    return lhs[1] < rhs[1];
}

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        std::sort(intervals.begin(), intervals.end(), compare);
        int N = intervals.size();
        if (N == 0) return 0;
        vector<int> dp(N, 1);
        for (int i = 1; i < N; ++i) {
            for (int j = i - 1; j >= 0; --j) {
                if (intervals[j][1] <= intervals[i][0]) {
                    dp[i] = dp[j] + 1;
                    break;
                }
            }
            dp[i] = max(dp[i], dp[i-1]);
        }
        return N - dp[N-1];
    }
};

贪心算法，简单地说就是：每一步都做出一个局部最优的选择，最终的结果恰好就是全局最优。

贪心算法是动态规划算法的一个特例，相比动态规划，贪心算法需要满足的条件更加严苛，但是效率比动态规划要高。是否满足贪心算法的条件，要根据题目的特征来判断。

比如有 100 个硬币，你只能拿 10 个，如何拿到最大值？每次都选择剩余硬币中面额最大的（局部最优），最后的结果恰好是全局最优。

这道题是可以用贪心算法实现的。

474-一和零

给定不同的“01”字符串数组，计算最多有 m 个 0 和 n 个 1 的最大子集的大小。

例如 ["10", "0001", "111001", "1", "0"], m = 5, n = 3；最大子集是 0，答案为 4。

最优子结构：设 dp[i][j] 为 i 个 0 和 j 个 1，最多能拼出的字符串数目。

状态转移方程：枚举每个字符串，对每个字符串，都有两种选择：

• 不选则 dp[i][j] 保持不变；
• 选则 dp[i][j] = 1 + dp[i-cnt0][j-cnt1];（1 代表当前枚举的字符串本身）。

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m+1, vector<int>(n+1));
        for (const string &s : strs) {
            int cnt0 = count(s.begin(), s.end(), '0');
            int cnt1 = count(s.begin(), s.end(), '1');
            for (int i = m; i >= cnt0; --i) {
                for (int j = n; j >= cnt1; --j) {
                    dp[i][j] = max(dp[i][j], 1 + dp[i-cnt0][j-cnt1]);
                }
            }
        }
        return dp[m][n];
    }
};

494-目标和

给定一个数组（非负）和一个目标数，对于数组中任意一个数你可以选择符号 + 或 -，问有多少种方法使得和为目标数。

我们把这个数组分为 A 和 B 两部分，对 A 全部取 +，对 B 全部取 -，则应满足 sum(A) - sum(B) = target。

等式两边各加上 2 * sum(B)，得到 sum(A) + sum(B) = target + sum(B)，其中 sum(A) + sum(B) 就是数组所有数的和。

于是我们将问题转化为：是否存在一个子集 B，使得 sum(nums) = target + 2 * sum(B)。接下来的思路就和分割等和子集一样了。

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int target = S;
        S = accumulate(nums.begin(), nums.end(), 0);
        if ((S - target) & 1) return 0;
        target = (S - target) / 2;
        if (target < 0) return 0;
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for (int num : nums) {
            for (int i = target; i >= num; --i) {
                dp[i] += dp[i-num];
            }
        }
        return dp[target];
    }
};

583-使两个字符串相同

给定两个字符串，找到使得它们相同的最小步数，每步可以删除任意一个字符串中的一个字符。

分别删除两个字符串中的字符使它们一样，实际上就是上一题的问题——找最长公共子序列。找到了 LCS，把其它字符删掉就可以了。

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        M = len(word1)
        N = len(word2)
        dp = [[0 for _ in range(N+1)] for _ in range(M+1)]
        for i in range(1, M+1):
            for j in range(1, N+1):
                if word1[i-1] == word2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        lcs = dp[M][N]
        res = M + N - lcs * 2
        return res

646-最长数对链

给定 n 个数对 (a, b)，其中 a < b。求最长数对链的长度。当 b < c 时，(c, d) 可以跟在 (a, b) 后面形成链。

650-复制粘贴字符

记事本上有一个字母 'A'，求最少的操作次数，在记事本中输出恰好 N 个 'A'。每一次操作可以复制全部或者粘贴。

718-最长重复子数组

给定两个数组，返回两个数组中公共的、长度最长的子数组的长度。

一、找最优子结构——问什么就设什么，设 dp[i][j] = 以 A[i-1] 和 B[j-1] 为结尾的最长重复子数组的长度。

二、找状态转移方程。两个数组一个作为行，一个作为列，画出表格。

由于子数组需要连续，因此 dp[i][j] = A[i-1] == B[j-1] ? (dp[i-1][j-1] + 1) : 0

class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int M = A.size();
        int N = B.size();
        vector<vector<int>> dp(M+1, vector<int>(N+1));
        int res = 0;
        for (int i = 1; i <= M; ++i) {
            for (int j = 1; j <= N; ++j) {
                if (A[i-1] == B[j-1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                res = max(res, dp[i][j]);
            }
        }
        return res;
    }
};

887-鸡蛋掉落

K 个鸡蛋，N 层楼，找到 F 满足任何从高于 F 的楼层落下的鸡蛋都会碎，从 F 楼层或比它低的楼层落下的鸡蛋都不会破。确定 F 的值的最小移动次数是多少？

如果只有一个鸡蛋，那么我们没有试错的机会，只能从第一层开始逐层尝试，需要尝试 N 次。

初始状态可以用 (K, N) 表示。当我们从 X 层扔下鸡蛋，如果鸡蛋破碎，则状态变为 (K-1, X-1)；如果鸡蛋完好，则状态变为 (K, N-X)。

我们可以穷举 X，并找到次数最少的移动方法，每一步的 X 即代表了应该从哪一层扔下鸡蛋。

class Solution:
    def superEggDrop(self, K: int, N: int) -> int:
        ## 如果我们只有一个鸡蛋，那么我们必须从第一层开始，逐层尝试，因为鸡蛋一旦打破，就没有鸡蛋再试，我们就无法找到问题的解。
        ## 因此在最坏情况下，我们需要尝试 N 次才得到问题的解。
        if K == 1: return N
        if N == 0: return 0 ## 边界条件
        res = float('INF') ## 取一个最大值
        ## 对于任意楼层 1 <= i <= N，存在两种情况，从 i 层扔下鸡蛋，摔碎或者没摔碎。
        for i in range(1, N+1):
            ## 在第 i 层摔碎了，鸡蛋数量-1，需尝试楼层变为 i-1
            broken = self.superEggDrop(K-1, i-1)
            ## 在第 i 层没摔碎，鸡蛋数量不变，需尝试楼层变为 N-i
            good = self.superEggDrop(K, N-i)
            ## 需考虑最坏情况下的移动次数，因此应该取两种情况下次数的较大者，再加上从 i 层扔下的这一次本身
            res = min(res, max(broken, good) + 1)
        return res

上述的代码可以计算出结果，但显然这个递归存在大量的重复计算，因此我们很自然地要用记忆化递归：

class Solution:
    cache = {}
    def superEggDrop(self, K: int, N: int) -> int:
        if K == 1: return N
        if N == 0: return 0
        if (K, N) in self.cache:
            return self.cache[(K, N)]
        res = float('INF')
        for i in range(1, N+1):
            ## 在第 i 层摔碎了，鸡蛋数量 -1，楼层从 i-1 层继续尝试
            broken = self.superEggDrop(K-1, i-1)
            ## 在第 i 层没摔碎，鸡蛋数量不变，楼层从 i+1 层继续尝试
            good = self.superEggDrop(K, N-i)
            res = min(res, max(broken, good) + 1)
        self.cache[(K, N)] = res
        return res

经过改造后，减少了大量的重复计算，但是针对 K = 4，N = 2000 这种测试用例时，仍然会超时，且超出了 python3 的默认最大递归深度。我们还需要更优化的方法。

解题的亮点来了，我们之前采用的方法是穷举 X，注意 dp(K-1, X-1) 和 dp(K, N-X) 这两个函数，如果 K, N 固定，把这两个函数看作关于 X 的函数，那么 dp(K-1, X-1) 是在第一象限的单调递增函数，而 dp(K, N-X) 是在第一象限的单调递减函数。

max(dp(K-1, X-1), dp(K, N-X)) 是图中红色的线，这条线上的最小值就是此题的解。很显然，我们并不需要穷举 X，只需要二分查找 X 即可：

class Solution:
    cache = {}
    def superEggDrop(self, K: int, N: int) -> int:
        if K == 1: return N
        if N == 0: return 0
        if (K, N) in self.cache:
            return self.cache[(K, N)]
        res = float('INF')
        lo = 1
        hi = N
        while lo <= hi:
            mid = (lo + hi) // 2
            broken = self.superEggDrop(K-1, mid-1)
            good = self.superEggDrop(K, N-mid)
            if broken > good:
                hi = mid - 1
                res = min(res, broken + 1)
            else:
                lo = mid + 1
                res = min(res, good + 1)
        self.cache[(K, N)] = res
        return res

1143-最长公共子序列

最长公共子序列（Longest common subsequence），是指字符串 text1 和 text2 共同拥有的子序列。

首先，先写出基础的递归方法：

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        return self.dfs(text1, text2, 0, 0)

    def dfs(self, text1, text2, i, j):
        if i == len(text1) or j == len(text2):
            ## 到达字符串末尾
            return 0
        if text1[i] == text2[j]:
            ## 找到一个公共字符
            return self.dfs(text1, text2, i+1, j+1) + 1
        else:
            left = self.dfs(text1, text2, i+1, j) ## text1[i] 不在 LCS 中的情况
            right = self.dfs(text1, text2, i, j+1) ## text2[j] 不在 LCS 中的情况
            return max(left, right) ## 两者取较大值

这个递归方法存在着大量的重复计算，递归树的高度 N = min(len(text1), len(text2))，算法复杂度为 O(2^N)，这太大了，我们还是尝试用记忆化递归的方式来剪枝。

## 结果：1992 ms, 在所有 Python3 提交中击败了 5.03% 的用户。
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        cache = {}
        return self.dfs(text1, text2, 0, 0, cache)

    def dfs(self, text1, text2, i, j, cache):
        if i == len(text1) or j == len(text2):
            ## 到达字符串末尾
            return 0
        if (i, j) in cache:
            return cache[(i, j)]
        if text1[i] == text2[j]:
            ## 找到一个公共字符
            cache[(i, j)] = self.dfs(text1, text2, i+1, j+1, cache) + 1
            return cache[(i, j)]
        else:
            cache[i+1, j] = self.dfs(text1, text2, i+1, j, cache) ## text1[i] 不在 LCS 中的情况
            cache[i, j+1] = self.dfs(text1, text2, i, j+1, cache) ## text2[j] 不在 LCS 中的情况
            cache[i, j] = max(cache[i+1, j], cache[i, j+1])
            return cache[i, j] ## 两者取较大值

考虑用动态规划，自底向上构建出问题的解。

一、找最优子结构——问什么就设什么，设 dp[i][j] = text1[0...i-1] 与 text2[0...j-1] 的最长公共子序列的长度，表格如下：

二、找状态转移方程。

对于 s1 和 s2 中的每个字符，有两种选择，要么在 LCS 中，要么不在。

如果 s1[i-1] == s2[j-1]，那么这是一个公共字符，dp[i][j] = dp[i-1][j-1] + 1

反之，s1[i-1]、s2[j-1] 至少有一个不在 LCS 中，dp[i][j] = max(dp[i-1][j], dp[i][j-1])

class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        M = len(text1)
        N = len(text2)
        dp = [[0 for i in range(N+1)] for i in range(M+1)]
        for i in range(1, M+1):
            for j in range(1, N+1):
                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[M][N]

1478-分配邮筒

houses[i] 代表第 i 个房子在一条街上的位置，现需要在这条街上安排 k 个邮筒，求每栋房子与离它最近的邮筒之间的距离的最小总和。

这道题是很明显的动态规划题，房子一个一个选，邮筒一个一个增加。在给动态规划画表格的时候，哪个是行哪个是列呢？我发现一个规律，列的元素在数轴上是连续的，比如背包容量、本题中的邮筒数量。行的元素可以不连续的，比如硬币的选择、本题中房子的位置等。

因此，可设最优子结构 dp[i][j] 为 house[0...i] 分配 j 个邮筒的距离最小总和。

股票交易

121-买卖股票

给定一组股票价格，只能买卖一次，求最大收益。

在一次遍历中，记录最低的价格，动态计算最大差值即可。

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

122-买卖股票 II

给定一组股票价格，买卖次数不限，求最大收益。买入股票前，必须先卖出持有的。

只要第二天的价格比第一天的高，就可以获取一次价差。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;
        for (int i = 1; i < prices.size(); ++i) {
            if (prices[i] > prices[i-1]) {
                res += prices[i] - prices[i-1];
            }
        }
        return res;
    }
};

123-买卖股票 III

给定一组股票价格，只能交易两次，求最大收益。买入股票前，必须先卖出持有的。