算法解释

动态规划（Dynamic Programming, DP）在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间

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

在一些情况下，动态规划可以看成是带有状态记录（memoization）的优先搜索。状态记录的意思为，如果一个子问题在优先搜索时已经计算过一次，我们可以把它的结果储存下来，之后遍历到该子问题的时候可以直接返回储存的结果。动态规划是自下而上的，即先解决子问题，再解决父问题；而用带有状态记录的优先搜索是自上而下的，即从父问题搜索到子问题，若重复搜索到同一个子问题则进行状态记录，防止重复计算。如果题目需求的是最终状态，那么使用动态规划比较方便；如果题目需要输出所有的路径，那么使用带有状态记录的优先搜索会比较方便。

一维dp

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2

示例 2：

输入：n = 3
输出：3

问题可以分解为两大类，第一类，最后一步爬了两个台阶，第二类，最后一步爬了一个台阶。设 $f(k)$ 为上到 k 阶台阶的总方案数，则状态转移方程为 $f(k)=f(k-1)+f(k-2)$

代码 
1
2
3
4
5
6
7
8
9
10
int climbStairs(int n) {
    if (n <= 2)
        return n;
    vector<int> dp(n+1, 0);
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++)
        dp[i] = dp[i - 1] + dp[i - 2];
    return dp[n];
}

可以看出，就是斐波那契数列问题，可以进行空间压缩，重复利用存储空间，代码如下：

1
2
3
4
5
6
7
8
9
10
11
int climbStairs(int n) {
    if (n <= 2) 
        return n;
    int pre2 = 1, pre1 = 2, cur;
    for (int i = 2; i < n; i++) {
        cur = pre1 + pre2;
        pre2 = pre1;
        pre1 = cur;
    }
    return cur;
}

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你不触动警报装置的情况下，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4

示例 2：

输入：[2,7,9,3,1]
输出：12

设共有 k 个房间，有两种获得最高总金额的可能。

一是偷了第 k 个房间，总金额为前 k-2 个房间的最高总金额加上第 k 个房间的金额；二是没偷第 k 个房间，总金额为前 k-1 个房间的最高总金额，取两者中的较大者。设最高总金额为 $f(k)$，则状态转移方程为 $f(k)=max(f(k-2)+value[k],\quad f(k-1))$.

边界条件为 $f(1)=value[1] ,\quad f(2)=max(value[1],\quad value[2]).$

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
int rob(vector<int>& nums) {
    if (nums.empty())
        return 0;
    int size = nums.size();
    if (size == 1)
        return nums[0];
    vector<int> dp = vector<int>(size, 0);
    dp[0] = nums[0];
    dp[1] = max(nums[0], nums[1]);
    for (int i = 2; i < size; i++)
        dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
    return dp[size - 1];
}

同样可以进行空间压缩，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int rob(vector<int>& nums) {
    if (nums.empty()) 
        return 0;
    int n = nums.size();
    if (n == 1) 
        return nums[0];
    int pre2 = 0, pre1 = 0, cur;
    for (int i = 0; i < n; i++) {
        cur = max(pre2 + nums[i], pre1);
        pre2 = pre1;
        pre1 = cur;
    }
    return cur;
}

等差数列划分

如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。给你一个整数数组 nums，返回数组 nums 中所有为等差数组的子数组个数。

子数组是数组中的一个连续序列。

示例 1：

输入：nums = [1,2,3,4]
输出：3

示例 2：

输入：nums = [1]
输出：0

这道题略微特殊，因为要求是等差数列，可以很自然的想到子数组必定满足 num[i]-num[i-1] = num[i-1]-num[i-2]。定义以数字 nums[i] 结尾的等差子数组个数为 dp[i]，最后对 dp 数组求和即可。

代码 
1
2
3
4
5
6
7
8
9
10
11
int numberOfArithmeticSlices(vector<int>& nums) {
	int n = nums.size();
	if (n < 3) 
        return 0;
	vector<int> dp(n, 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;
	}
	return accumulate(dp.begin(), dp.end(), 0);
}

二维dp

最小路径和

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

说明：每次只能向下或者向右移动一步。

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

二维dp就建立二维数组，dp[i][j] 表示从左上角到位置 [i,j] 的最小路径和，

状态转移方程为 $dp[i][j]=min(dp[i-1][j],\quad dp[i][j-1])+grid[i][j]$，注意边界。

边界条件为 $dp[0][0]=grid[0][0]$.

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0)
                dp[i][j] = grid[i][j]; 
            else if (i == 0)
                dp[i][j] = dp[i][j-1] + grid[i][j]; 
            else if (j == 0)
                dp[i][j] = dp[i-1][j] + grid[i][j];
            else
                dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
        }
    }
    return dp[m-1][n-1];
}

同样可以进行空间压缩至一维，因为 dp 矩阵的每一个值只和左边和上面的值相关，当我们遍历到第 i 行第 j 列时，第 j-1 列已经更新过了，现在的 dp[j-1] 代表 dp[i][j-1] 的值；d[j] 待更新，现在的 dp[j] 代表 dp[i-1][j] 的值。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int minPathSum(vector<vector<int>>& grid) {
    int m = grid.size(), n = grid[0].size();
    vector<int> dp(n, 0);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (i == 0 && j == 0)
                dp[j] = grid[i][j];
            else if (i == 0)
                dp[j] = dp[j-1] + grid[i][j];
            else if (j == 0)
                dp[j] = dp[j] + grid[i][j];
            else
                dp[j] = min(dp[j], dp[j-1]) + grid[i][j];
        }
    }
    return dp[n-1];
}

“01”矩阵

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

示例 1：

输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]

示例 2：

输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]

dp[i][j] 表示位置 [i,j] 的元素到最近的 0 的距离，如果限制只能向右下搜索，则状态转移方程为：

左上同理，取最小值即可。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
    if (matrix.empty()) 
        return {};
    int n = matrix.size(), m = matrix[0].size();
    // 初始化动态规划的数组，所有的距离值都设置为一个很大的数
    vector<vector<int>> dp(n, vector<int>(m, INT_MAX - 1));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (matrix[i][j] == 0)
                dp[i][j] = 0;
            else {
              	//这样写就不用单独写特例了
                if (j > 0)
                    dp[i][j] = min(dp[i][j], dp[i][j-1] + 1);
                if (i > 0)
                    dp[i][j] = min(dp[i][j], dp[i-1][j] + 1);
            }
        }
    }
    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            if (matrix[i][j] != 0) {
                if (j < m - 1)
                    dp[i][j] = min(dp[i][j], dp[i][j+1] + 1);
                if (i < n - 1)
                    dp[i][j] = min(dp[i][j], dp[i+1][j] + 1);
            }
        }
    }
    return dp;
}

最大正方形

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

示例 1：

输入：matrix = [[“1”,”0”,”1”,”0”,”0”],[“1”,”0”,”1”,”1”,”1”],[“1”,”1”,”1”,”1”,”1”],[“1”,”0”,”0”,”1”,”0”]]
输出：4

示例 2：

输入：matrix = [[“0”,”1”],[“1”,”0”]]
输出：1

示例 3：

输入：matrix = [[“0”]]
输出：0

dp[i][j] 为以 [i,j] 为右下角的正方形的最大边长，若 matrix[i][j] = 0，则 dp[i][j] = 0；否则我们假设 dp[i][j] = k，其充分条件为 dp[i-1][j-1]、dp[i][j-1] 和 dp[i-1][j] 的值必须都不小于 k−1，否则 [i,j] 位置不可以构成一个面积为 $k^2$ 的正方形。同理，如果这三个值中的最小值为 k−1，则 [i,j] 位置一定且最大可以构成一个面积为 $k^2$ 的正方形。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int maximalSquare(vector<vector<char>>& matrix) {
	if (matrix.empty() || matrix[0].empty())
		return 0;
	int m = matrix.size(), n = matrix[0].size(), max_side = 0;
	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 (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;
			max_side = max(max_side, dp[i][j]);
		}
	}
	return max_side * max_side;
}

分割类型题

完全平方数

完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

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

示例 1：

输入：n = 12
输出：3

示例 2：

输入：n = 13
输出：2

对于分割类型题，动态规划的状态转移方程通常并不依赖相邻的位置，而是依赖于满足分割条件的位置。我们定义一个一维矩阵 dp，其中 dp[i] 表示数字 i 最少可以由几个完全平方数相加构成。在本题中，位置 i 只依赖 $i - k^2$ 的位置，如 i - 1、i - 4、i - 9 等等，才能满足完全平方分割的条件。因此，状态转移方程为：

代码 
1
2
3
4
5
6
7
8
9
int numSquares(int n) {
    vector<int> dp(n + 1, INT_MAX);
    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];
}

解码方法

一条包含字母 A-Z 的消息通过以下映射进行了编码：

‘A’ -> “1”
‘B’ -> “2”
…
‘Z’ -> “26”

要解码已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，”11106” 可以映射为：

“AAJF” ，将消息分组为 (1 1 10 6)
“KJF” ，将消息分组为 (11 10 6)

注意，消息不能分组为 (1 11 06)，因为 “06” 不能映射为 “F”，这是由于 “6” 和 “06” 在映射中并不等价。

给你一个只含数字的非空字符串 s，请计算并返回解码方法的总数 。

题目数据保证答案肯定是一个 32 位的整数。

示例 1：

输入：s = “12”
输出：2

示例 2：

输入：s = “226”
输出：3

示例 3：

输入：s = “0”
输出：0

就是要把一个大数字分割为一堆 1-26 的数字，设 dp[i] 表示字符串前 i 个字符的解码方法数，则状态转移方程为：

重叠部分叠加即可，注意数组下标从 0 开始。边界条件为 dp[0] = 1。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int numDecodings(string s) {
    int n = s.length();
    if (n == 0 || s[0] == '0')
        return 0;
    vector<int> dp(n+1, 0);
    dp[0] = 1;
    for (int i = 1; i <= n; i++) {
        if (s[i-1] != '0')
            dp[i] += dp[i-1];
        if (i > 1 && s[i-2] != '0' && (s[i-2] - '0') * 10 + (s[i-1] - '0') <= 26)
            dp[i] += dp[i-2]; 
    }
    return dp[n];
}

单词拆分

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s。s 和 wordDict[i] 仅有小写英文字母组成，wordDict 中的所有字符串互不相同。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

输入: s = “leetcode”, wordDict = [“leet”, “code”]
输出: true

示例 2：

输入: s = “applepenapple”, wordDict = [“apple”, “pen”]
输出: true

示例 3：

输入: s = “catsandog”, wordDict = [“cats”, “dog”, “sand”, “and”, “cat”]
输出: false

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

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
bool wordBreak(string s, vector<string>& wordDict) {
    int n = s.length();
    vector<bool> dp(n + 1, false);
    dp[0] = true;
    for (int i = 1; i <= n; i++) {
        for (const string & word: wordDict) {
            int len = word.length();
            if (i >= len && s.substr(i - len, len) == word)
                dp[i] = dp[i] || dp[i - len];
        }
    }
    return dp[n];
}

子序列问题

最长递增子序列

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

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1

对于子序列问题，第一种动态规划方法是，定义一个 dp 数组，其中 dp[i] 表示以 i 结尾的符合某性质的子序列的个数。在处理好每个位置后，统计一遍各个位置的结果即可得到题目要求的结果。

在本题中，dp[i] 可以表示以 i 结尾的、最长递增子序列长度。对于每一个位置 i，如果其之前的某个位置 j 所对应的数字小于位置 i 所对应的数字，则我们可以获得一个以 i 结尾的、长度为 dp[j]+1 的子序列。为了遍历所有情况，我们需要 i 和 j 进行两层循环，其时间复杂度为 O($n^2$)。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int lengthOfLIS(vector<int>& nums) {
    int max_length = 0, n = nums.size();
    if (n <= 1) 
        return n;
    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], dp[j] + 1);
        }
        max_length = max(max_length, dp[i]);
    }
    return max_length;
}

本题还可以使用二分查找将时间复杂度降低为 O(n log n)。我们定义一个 dp 数组，其中 dp[k] 存储长度为 k+1 的最长递增子序列的最后一个数字。我们遍历每一个位置 i，如果其对应的数字大于 dp 数组中所有数字的值，那么我们把它放在 dp 数组尾部，表示最长递增子序列长度加 1；如果我们发现这个数字在 dp 数组中比数字 a 大、比数字 b 小，则我们将 b 更新为此数字，使得之后构成递增序列的可能性增大。以这种方式维护的 dp 数组永远是递增的，因此可以用二分查找加速搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int lengthOfLIS(vector<int>& nums) {
    int n = nums.size();
    if (n <= 1) 
        return n;
    vector<int> dp;
    dp.push_back(nums[0]);
    for (int i = 1; i < n; i++) {
        if (dp.back() < nums[i])
            dp.push_back(nums[i]);
        else {
            auto itr = lower_bound(dp.begin(), dp.end(), nums[i]);
            *itr = nums[i];
        }
    }
    return dp.size();
}

最长公共子序列

给定两个仅由小写英文字母组成的字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回 0。

一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。

两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

示例 1：

输入：text1 = “abcde”, text2 = “ace”
输出：3

示例 2：

输入：text1 = “abc”, text2 = “abc”
输出：3

示例 3：

输入：text1 = “abc”, text2 = “def”
输出：0

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

在本题中，我们可以建立一个二维数组 dp，其中 dp[i][j] 表示到第一个字符串位置 i 为止、到第二个字符串位置 j 为止、最长的公共子序列长度。这样一来我们就可以很方便地分情况讨论这两个位置对应的字母相同与不同的情况了。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
int longestCommonSubsequence(string text1, string text2) {
    int m = text1.length(), n = text2.length();
    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-1][j], dp[i][j-1]);
        }
    }
    return dp[m][n];
}

背包问题

背包问题是一种组合优化的 NP 完全问题：有 N 个物品和容量为 W 的背包，每个物品都有自己的体积 w 和价值 v，求拿哪些物品可以使得背包所装下物品的总价值最大。如果限定每种物品只能选择 0 个或 1 个，则问题称为 0-1 背包问题；如果不限定每种物品的数量，则问题称为无界背包问题或完全背包问题。

1.“0-1”背包问题

我们可以用动态规划来解决背包问题。以 0-1 背包问题为例。我们可以定义一个二维数组 dp 存储最大价值，其中 dp[i][j] 表示前 i 件物品体积不超过 j 的情况下能达到的最大价值。在我们遍历到第 i 件物品时，在当前背包总容量为 j 的情况下，如果我们不将物品 i 放入背包，那么 dp[i][j] = dp[i-1][j]，即前 i 个物品的最大价值等于只取前 i-1 个物品时的最大价值；如果我们将物品 i 放入背包，假设第 i 件物品体积为 w，价值为 v，那么我们得到 dp[i][j] = dp[i-1][j-w] + v。我们只需在遍历过程中对这两种情况取最大值即可，总时间复杂度和空间复杂度都为 O(NW)。

dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v)

转化为代码语言如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
int knapsack(vector<int> weights, vector<int> values, int N, int W) {
    vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= N; i++) {
        int w = weights[i-1], v = values[i-1];
        for (int j = 1; j <= W; j++) {
            if (j >= w)
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-w] + v);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    return dp[N][W];
}

我们可以进一步对 0-1 背包进行空间优化，将空间复杂度降低为 O(W)。从状态转移方程可以看出，考虑第 i 个物品时，只与上一行有关，因此我们可以去掉 dp 矩阵的第一个维度，在考虑物品 i 时变成 dp[j] = max(dp[j], dp[j-w] + v)。这里要注意我们在遍历每一行的时候必须逆向遍历，这样才能够调用上一行物品 i-1 时 dp[j-w] 的值；若按照从左往右的顺序进行正向遍历，则 dp[j-w] 的值在遍历到 j 之前就已经被更新成物品 i 的值了。

1
2
3
4
5
6
7
8
9
int knapsack(vector<int> weights, vector<int> values, int N, int W) {
    vector<int> dp(W + 1, 0);
    for (int i = 1; i <= N; i++) {
        int w = weights[i-1], v = values[i-1];
        for (int j = W; j >= w; j--)
            dp[j] = max(dp[j], dp[j-w] + v);
    }
    return dp[W];
}

2.完全背包问题

在完全背包问题中，一个物品可以拿多次。假设物品体积均为 2，假设我们遍历到物品 i = 2 且其体积为 w = 2，价值为 v = 3；对于背包容量 j = 5，最多只能装下 2 个该物品。那么我们的状态转移方程就变成了 dp[2][5] = max(dp[1][5], dp[1][3] + 3, dp[1][1] + 6)。如果采用这种方法，假设背包容量无穷大而物体的体积无穷小，我们这里的比较次数也会趋近于无穷大，远超 O(NW) 的时间复杂度。

怎么解决这个问题呢？我们发现在 dp[2][3] 的时候我们其实已经考虑了 dp[1][3] 和 dp[2][1] 的情况，而在 dp[2][1] 也已经考虑了 dp[1][1] 的情况。因此，对于拿多个物品的情况，我们只需考虑 dp[2][3] 即可，即 dp[2][5] = max(dp[1][5], dp[2][3] + 3)。这样，我们就得到了完全背包问题的状态转移方程：

dp[i][j] = max(dp[i-1][j], dp[i][j-w] + v)

其与 0-1 背包问题的差别仅仅是把状态转移方程中的第二个 i-1 变成了 i。

1
2
3
4
5
6
7
8
9
10
11
12
13
int knapsack(vector<int> weights, vector<int> values, int N, int W) {
    vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= N; i++) {
        int w = weights[i-1], v = values[i-1];
        for (int j = 1; j <= W; j++) {
            if (j >= w)
                dp[i][j] = max(dp[i-1][j], dp[i][j-w] + v);
            else
                dp[i][j] = dp[i-1][j];
        }
    }
    return dp[N][W];
}

同样的，我们也可以利用空间压缩将时间复杂度降低为 O(W)。这里要注意我们在遍历每一行的时候必须正向遍历，因为我们需要利用当前物品在第 j-w 列的信息。

1
2
3
4
5
6
7
8
9
int knapsack(vector<int> weights, vector<int> values, int N, int W) {
    vector<int> dp(W + 1, 0);
    for (int i = 1; i <= N; i++) {
        int w = weights[i-1], v = values[i-1];
        for (int j = w; j <= W; j++)
            dp[j] = max(dp[j], dp[j-w] + v);
    }
    return dp[W];
}

分割等和子集

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

示例 1：

输入：nums = [1,5,11,5]
输出：true

示例 2：

输入：nums = [1,2,3,5]
输出：false

等价于“0-1”背包问题，输出是否可以取出总和正好为 sum/2 的数字，把数字大小看做体积，不用考虑价值，dp[i][j] 表示是否能正好取出体积为 j 的物品

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool canPartition(vector<int>& nums) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % 2)
        return false;
    int target = sum / 2, n = nums.size();
    vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));
    dp[0][0] = true;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= target; 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][target];
}

空间压缩如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool canPartition(vector<int>& nums) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if (sum % 2)
        return false;
    int target = sum / 2, n = nums.size();
    vector<bool> dp(target + 1, false);
    dp[0] = true;
    for (int i = 1; i <= n; i++) {
        for (int j = target; j >= nums[i-1]; j--) {
            dp[j] = dp[j] || dp[j-nums[i-1]];
        }
    }
    return dp[target];
}

一和零

给你一个二进制字符串数组 strs 和两个整数 m 和 n。请你找出并返回 strs 的最大子集的长度，该子集最多有 m 个 0 和 n 个 1。如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集 。

示例 1：

输入：strs = [“10”, “0001”, “111001”, “1”, “0”], m = 5, n = 3
输出：4

示例 2：

输入：strs = [“10”, “0”, “1”], m = 1, n = 1
输出：2

这里有两个不同维度的体积，dp[i][j][k] 表示在遍历到第 i 个物品时，在 0 的个数小于等于 m，1 的个数小于等于 n 时，所能取到的最大子集长度，则状态转移方程为：

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
pair<int, int> count(const string & s){
    int count0 = s.length(), count1 = 0;
    for (const char & c: s) {
        if (c == '1') {
            count1++;
            count0--;
        }
    }
    return make_pair(count0, count1);
}
int findMaxForm(vector<string>& strs, int m, int n) {
    int length = strs.size();
    vector<vector<vector<int>>> dp(length + 1, vector<vector<int>>(m + 1, vector<int>(n + 1)));
    for (int i = 1; i <= length; i++) {
        auto [zeros, ones] = count(strs[i-1]);
        for (int j = 0; j <= m; j++) {
            for (int k = 0; k <= n; k++) {
                if (j < zeros || k < ones)
                    dp[i][j][k] = dp[i-1][j][k];
                else
                    dp[i][j][k] = max(dp[i-1][j][k], dp[i-1][j-zeros][k-ones] + 1);
            }
        }
    }
    return dp[length][m][n];
}

零钱兑换

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

你可以认为每种硬币的数量是无限的。

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

完全背包问题，dp[i] 表示总金额为 i 时的最少硬币个数，则状态转移方程为：

因为遍历 j 时会实时更新 dp[i] 的值，所以方程变为：

为了避免dp[i]刚开始就被取到，初始值取为amount + 1，同时也可以判断最后是否输出 -1。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
int coinChange(vector<int>& coins, int amount) {
    if (coin.empty())
        return -1;
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;
    for (int i = 1; i <= amount; i++) {
        for (int& coin : coins) {
            if (i >= coin)
                dp[i] = min(dp[i], dp[i-coin] + 1);
        }
    }
    return (dp[amount] == amount + 1) ? -1 : dp[amount]
}

字符串编辑

编辑距离

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

示例 1：

输入：word1 = “horse”, word2 = “ros”
输出：3

示例 2：

输入：word1 = “intention”, word2 = “execution”
输出：5

类似于题目 1143，我们使用一个二维数组 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。边界条件为 dp[0][j] = j，dp[i][0] = i

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int minDistance(string word1, string word2) {
    int m = word1.length(), n = word2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0)
                dp[i][j] = j;
            else if (j == 0)
                dp[i][j] = i;
            else
                dp[i][j] = min(dp[i-1][j-1] + ((word1[i-1] == word2[j-1]) ? 0 : 1), min(dp[i][j-1] + 1, dp[i-1][j] + 1));
        }
    }
    return dp[m][n];
}

只有两个键的键盘

最初记事本上只有一个字符 ‘A’。你每次可以对这个记事本进行两种操作：

Copy All（复制全部）：复制这个记事本中的所有字符（不允许仅复制部分字符）。
Paste（粘贴）：粘贴上一次复制的字符。

给你一个数字 n，你需要使用最少的操作次数，在记事本上输出恰好 n 个 ‘A’。返回能够打印出 n 个 ‘A’ 的最少操作次数。

示例 1：

输入：3
输出：3

示例 2：

输入：1
输出：0

不同于以往通过加减实现的动态规划，这里需要乘除法来计算位置，因为粘贴操作是倍数增加的。设 dp[i] 表示得到 i 个 ‘A’ 的最少操作数，要得到 i 个，对于 i 的因子 j，从 j 个到 i 个最少操作次数等价于 1 到 i/j，即 dp[i/j]，从 1 到 j 最少操作次数为 dp[j]，所以状态转移方程为：

若 i 为素数，则只能通过一次复制，若干次粘贴得到，故边界条件为 dp[i] = i。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
int minSteps(int n) {
    vector<int> dp(n + 1);
    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];
}

正则表达式匹配

给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖整个字符串 s 的，而不是部分字符串。

示例 1：

输入：s = “aa”, p = “a”
输出：false

示例 2:

Input: s = “aab”, p = “c*a*b”
Output: true
我们可以重复 c 零次，重复 a 两次。

示例 3：

输入：s = “ab”, p = “.*“
输出：true

提示：

  • s 只包含从 a-z 的小写字母。
  • p 只包含从 a-z 的小写字母，以及字符 . 和 *。
  • 保证每次出现字符 * 时，前面都匹配到有效的字符

我们可以使用一个二维数组 dp，其中 dp[i][j] 表示以 i 截止的字符串是否可以被以 j 截止的正则表达式匹配。根据正则表达式的不同情况，即字符、星号，点号，我们可以分情况讨论来更新 dp 数组。状态转移方程如下：

其中 p[j] = ‘*’ 时的情况比较复杂，本质上只有两种操作方式：

  • 匹配一次后继续向前匹配，即 dp[i-1][j]，s[i]=s[i-1]=···=p[j-1]的情况。
  • 匹配0次，扔掉p[j-1]和’*’，继续比较，即 dp[i][j-2]。

代码如下，注意数组下标。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
bool isMatch(string s, string p) {
    int m = s.size(), n = p.size(), i, j;
    vector<vector<int>> dp(m+1, vector<int>(n+1, false));
    dp[0][0] = true;//空串能够匹配
    for(i = 0; i <= m; i++) {
        for(j = 1; j <= n; j++) {
            if(p[j-1] == '*') {
                dp[i][j] |= dp[i][j-2];//*匹配0次前面的字符
                if(match(s,p,i,j-1)) //s第i个和p的第j-1个可以匹配, *匹配再多匹配一次i字符
                    dp[i][j] |= dp[i-1][j];
            }
            else {
                if(match(s,p,i,j))//必须是i、j能够匹配
                    dp[i][j] |= dp[i-1][j-1];
            }
        }
    }
    return dp[m][n];
}
bool match(string &s, string &p, int i, int j)  {   //第i,j个字符能匹配
    return i>0 && (p[j-1] == '.' || p[j-1] == s[i-1]);
}

股票交易

买卖股票的最佳时期

给定一个数组 prices，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0。

示例 1：

输入：[7,1,5,3,6,4]
输出：5

示例 2：

输入：prices = [7,6,4,3,1]
输出：0

我们可以遍历一遍数组，在每一个位置 i 时，记录 i 位置之前所有价格中的最低价格，然后将当前的价格作为售出价格，查看当前收益是不是最大收益即可。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int maxProfit(vector<int>& prices) {
    int n = prices.size();
    vector<int> dp(n + 1);
    dp[1] = prices[0];
    int max = 0;
    for (int i = 1; i < n; i++) {
        if (prices[i] < dp[i])
            dp[i+1] = prices[i];
        else {
            dp[i+1] = dp[i];
            if (prices[i] - dp[i+1] > max)
                max = prices[i] - dp[i+1];
        }
    }
    return max;
}

实际上记录最低价用一个变量即可，这里只是为了DP而DP

买卖股票的最佳时机IV

给定一个整数数组 prices，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1：

输入：k = 2, prices = [2,4,1]
输出：2

示例 2：

输入：k = 2, prices = [3,2,6,5,0,3]
输出：7

如果 k 大于总天数的一半，那么我们一旦发现可以赚钱就可以进行买卖；这里一半的原因是因为当天股价是不变的，因此一次买卖需要两天。如果 k 小于总天数，我们用 buy[i][j] 表示对于数组 prices[0..i] 中的价格而言，进行恰好 j 笔交易，并且当前手上持有一支股票，这种情况下的最大利润；用 sell[i][j] 表示恰好进行 j 笔交易，并且当前手上不持有股票，这种情况下的最大利润。

为了方便分析，买入不算交易，卖出才算一次交易

那么我们可以对状态转移方程进行推导。对于 buy[i][j]，我们考虑当前手上持有的股票是否是在第 i 天买入的。可以得到状态转移方程：

同理对于 sell[i][j]，我们可以得到状态转移方程：

在上述的状态转移方程中，确定边界条件是非常重要的步骤。我们可以考虑将所有的 buy[0][0..k] 以及 sell[0][0..k] 设置为边界。

对于 buy[0][0..k]，由于只有 prices[0] 唯一的股价，因此我们不可能进行过任何交易，那么我们可以将所有的 buy[0][1..k] 设置为一个非常小的值，表示不合法的状态。而对于 buy[0][0]，它的值为 −prices[0]，即「我们在第 0 天以 prices[0] 的价格买入股票」是唯一满足手上持有股票的方法。

同理我们可以将所有的 sell[0][1..k] 设置为一个非常小的值，表示不合法的状态。而对于 sell[0][0]，它的值为 0，即「我们在第 0 天不做任何事」是唯一满足手上不持有股票的方法。

在设置完边界之后，我们就可以使用二重循环，在 i∈[1,n),j∈[0,k] 的范围内进行状态转移。需要注意的是，sell[i][j] 的状态转移方程中包含 buy[i−1][j−1]，在 j=0 时其表示不合法的状态，因此在 j=0 时，我们无需对 sell[i][j] 进行转移，让其保持值为 0 即可。

注意，不一定交易次数多了就利润高

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int maxProfit(int k, vector<int>& prices) {
    int days = prices.size();
    if (days < 2)
        return 0;
    if (k * 2 >= days)
        return maxProfitUnlimited(prices);
    vector<int> buy(k + 1, INT_MIN), sell(k + 1, INT_MIN/2);
    buy[0] = -prices[0];
    sell[0] = 0;
    for (int i = 1; i < days; i++) {
        for (int j = 0; j <= k; j++) {
            buy[j] = max(buy[j], sell[j] - prices[i]);
            if (j > 0)
                sell[j] = max(sell[j], buy[j-1] + prices[i]);
        }
    }
    return *max_element(sell.begin(), sell.end());
}
int maxProfitUnlimited(vector<int> prices) {
    int maxProfit = 0;
    for (int i = 1; i < prices.size(); i++) {
        if (prices[i] > prices[i-1])
            maxProfit += prices[i] - prices[i-1];
    }
    return maxProfit;
}

买卖股票之含冷冻期

给定一个整数数组 prices，其中第 prices[i] 表示第 i 天的股票价格。设计一个算法计算出最大利润。

在满足以下约束条件下，你可以尽可能地完成更多的交易：卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

示例 1:

输入: prices = [1,2,3,0,2]
输出: 3

示例 2:

输入: prices = [1]
输出: 0

考虑第 i 天结束后的情况，有三种状态：

  • 手里有一支股票，最大收益用 dp[i][0] 表示
  • 手里没有股票，今天刚卖掉，明天处于冷冻期，最大收益用 dp[i][1] 表示
  • 手里没有股票，早就卖掉了，明天不是冷冻期，最大收益用 dp[i][2] 表示

则状态转移方程为：

因为最后一天持有股票显然不是最大收益，所以最终答案为 max(dp[n][1], dp[n][2]);

考虑边界条件:

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int maxProfit(vector<int>& prices) {
    if (prices.empty())
        return 0;
    int n = prices.size();
    vector<vector<int>> dp(n+1, vector<int>(3));
    dp[1][0] = -prices[0];
    dp[1][1] = 0;
    dp[1][2] = 0;
    for (int i = 2; i <= n; i++) {
        dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i-1]);
        dp[i][1] = dp[i-1][0] + prices[i-1];
        dp[i][2] = max(dp[i-1][1], dp[i-1][2]);
    }
    return max(dp[n][1], dp[n][2]);
}

我们也可以使用状态机来解决这类复杂的状态转移问题，通过建立多个状态以及它们的转移方式，我们可以很容易地推导出各个状态的转移方程。如图所示，我们可以建立四个状态来表示带有冷却的股票交易，以及它们的之间的转移方式。

状态机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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]);
}

练习

打家劫舍II

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，今晚能够偷窃到的最高金额。

示例 1：

输入：nums = [2,3,2]
输出：3

示例 2：

输入：nums = [1,2,3,1]
输出：4

示例 3：

输入：nums = [1,2,3]
输出：3

与之前的区别在于若偷了第一间，则偷窃范围为1 ~ n-1，若没偷第一间，则偷窃范围为2 ~ n

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int rob(vector<int>& nums) {
    if (nums.empty())
        return 0;
    int n = nums.size();
    if (n == 1)
        return nums[0];
    if (n == 2)
        return max(nums[0], nums[1]);
    vector<int> dp1(n, 0), dp2(n, 0);
    dp1[1] = nums[0];
    dp2[1] = nums[1];
    for (int i = 2; i < n; i++) {
        dp1[i] = max(dp1[i-2] + nums[i-1], dp1[i-1]);
        dp2[i] = max(dp2[i-2] + nums[i], dp2[i-1]);
    }
    return max(dp1[n-1], dp2[n-1]);
}

最大子数组和

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

子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

dp[i] 表示以 nums[i] 结尾的连续子数组的最大和，则

代码 
1
2
3
4
5
6
7
8
int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n);
    dp[0] = nums[0];
    for (int i = 1; i < n; i++)
        dp[i] = max(dp[i-1] + nums[i], nums[i]);
    return *max_element(dp.begin(), dp.end());
}

可以将一维空间压缩为常量，考虑到 dp[i] 只和 dp[i-1] 相关，于是我们可以只用一个变量 pre 来维护对于当前 dp[i] 的 dp[i-1] 的值是多少，从而让空间复杂度降低到 O(1)

1
2
3
4
5
6
7
8
9
10
11
int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    int pre = nums[0], cur, Max = nums[0];
    for (int i = 1; i < n; i++) {
        cur = max(pre + nums[i], nums[i]);
        pre = cur;
        if (cur > Max)
            Max = cur;
    }
    return Max;
}

整数拆分

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

示例 1:

输入: n = 2
输出: 1

示例 2:

输入: n = 10
输出: 36

设 dp[i] 表示将 i 拆分后的最大乘积，假设将 i 拆分为 j 和 i-j，或者继续拆分，取较大值即可，即

代码 
1
2
3
4
5
6
7
8
9
10
11
int integerBreak(int n) {
    vector <int> dp(n + 1);
    dp[0] = dp[1] = 0;
    for (int i = 2; i <= n; i++) {
        int Max = 0;
        for (int j = 1; j < i; j++)
            Max = max(Max, max(j * (i - j), j * dp[i - j]));
        dp[i] = Max;
    }
    return dp[n];
}

两个字符串的删除操作

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

示例 1：

输入: word1 = “sea”, word2 = “eat”
输出: 2

示例 2:

输入：word1 = “leetcode”, word2 = “etco”
输出：4

dp[i][j] 表示使 word1[0:i] 和 word2[0:j] 相同的最少删除操作次数。

上述表示中，word[0:i]表示前 i 个元素

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int minDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
    for (int i = 1; i <= m; ++i)
        dp[i][0] = i;
    for (int j = 1; 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], dp[i][j - 1]) + 1;
        }
    }
    return dp[m][n];
}

压缩到一维，如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int minDistance(string word1, string word2) {
    int m = word1.size(), n = word2.size();
    vector<int> dp(n + 1);
    for (int j = 0; j <= n; j++)
        dp[j] = j;
    for (int i = 1; i <= m; i++) {
        int last = dp[0];
        dp[0] = i;
        for (int j = 1; j <= n; j++) {
            int old = dp[j];
            if (word1[i - 1] == word2[j - 1])
                dp[j] = last;
            else
                dp[j] = min(dp[j], dp[j - 1]) + 1;
            last = old;
        }
    }
    return dp[n];
}

注意：这里用last记录dp[i-1][j-1]，因为在正向遍历中它会先被更新为dp[i][j-1]

最长数对链

给出 n 个数对。在每一个数对中，第一个数字总是比第二个数字小。现在，我们定义一种跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。

给定一个数对集合，找出能够形成的最长数对链的长度。你不需要用到所有的数对，你可以以任何顺序选择其中的一些数对来构造。

示例：

输入：[[1,2], [2,3], [3,4]]
输出：2
解释：最长的数对链是 [1,2] -> [3,4]

dp[i] 表示以数对 i 结尾的最长数对链长度，则当 j > i 且 pairs[i][1] < pairs[j][0] 时有

代码 
1
2
3
4
5
6
7
8
9
10
11
12
int findLongestChain(vector<vector<int>>& pairs) {
    sort(pairs.begin(), pairs.end());
    int n = pairs.size();
    vector<int> dp(n+1, 1);
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            if (pairs[i][1] < pairs[j][0])
                dp[j] = max(dp[j], dp[i] + 1);
        }
    }
    return *max_element(dp.begin(), dp.end());
}

摆动序列

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如，[1, 7, 4, 9, 2, 5] 是一个摆动序列，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums，返回 nums 中作为摆动序列的最长子序列的长度。

示例 1：

输入：nums = [1,7,4,9,2,5]
输出：6

示例 2：

输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7

示例 3：

输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2

up[i] 表示范围 0~i 最长摆动子序列长度，末尾向上摆，down[i] 表示末尾向下摆，则

这里的状态转移方程可能很难理解，下面证明一下 up[i] 的式子，down同理：

当 nums[i]<=nums[i-1] 时，找不到比 up[i-1] 更长的了，因为任意以 nums[i] 结尾的末尾向上摆的都可以把 nums[i] 换成 nums[i-1]，且若不以 nums[i] 结尾，就等价于 up[i-1]，所以 up[i] = up[i-1]；

当 nums[i]>nums[i-1]，如果不取 nums[i]，则 up[i]=up[i-1]，如果取 nums[i]，则分别考虑如何从 up[i-1] 和 down[i-1] 转移过来，如果从 up[i-1] 转移过来，那么必须经过 down[i-1]，所以只考虑 down[i-1] 即可，设末尾元素为 nums[j]，若nums[j]>=nums[i-1]，则可以替换为nums[i-1]，后面接上 nums[i]，若 nums[j]<nums[i-1]，则可以直接在后面加上 nums[i]，总之就是 up[i] = down[i-1] + 1；

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int wiggleMaxLength(vector<int>& nums) {
    int n = nums.size();
    if (n <= 2) {
        if (n == 2 && nums[0] != nums[1])
            return 2;
        else 
            return 1;
    }
    vector<int> up(n, 1), down(n, 1);
    for (int i = 1; i < n; i++) {
        if (nums[i] > nums[i-1]) {
            up[i] = max(down[i-1] + 1, up[i-1]);
            down[i] = down[i-1];
        }
        else if (nums[i] < nums[i-1]) {
            down[i] = max(up[i-1] + 1, down[i-1]);
            up[i] = up[i-1];
        }
        else {
            up[i] = up[i-1];
            down[i] = down[i-1];
        }
    }
    return max(up[n-1], down[n-1]);
}

显然可以压缩为常量空间，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int wiggleMaxLength(vector<int>& nums) {
    int n = nums.size();
    if (n <= 2) {
        if (n == 2 && nums[0] != nums[1])
            return 2;
        else 
            return 1;
    }
    int up = 1, down = 1;
    for (int i = 1; i < n; i++) {
        if (nums[i] > nums[i-1])
            up = max(down + 1, up);
        else if (nums[i] < nums[i-1])
            down = max(up + 1, down);
    }
    return max(up, down);
}

目标和

给你一个整数数组 nums 和一个整数 target。向数组中的每个整数前添加 ‘+’ 或 ‘-‘，然后串联起所有整数，可以构造一个表达式：

例如，nums = [2, 1]，可以在 2 之前添加 ‘+’，在 1 之前添加 ‘-‘，然后串联起来得到表达式 “+2-1”。
返回可以通过上述方法构造的、运算结果等于 target 的不同表达式的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

输入：nums = [1], target = 1
输出：1

一个比较巧妙的方法，只考虑加法，剩下的全部做减法，设总和为 sum，则加法目标和为，然后就转化为了“0-1”背包问题。

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int findTargetSumWays(vector<int>& nums, int target) {
    int sum = accumulate(nums.begin(), nums.end(), 0);
    if ((sum + target) % 2 != 0)
        return 0;
    int n = (sum + target) / 2;
    if (n < 0)
        n = -n;
    vector<int> dp(n+1, 0);
    dp[0] = 1;
    for (int i = 1; i <= nums.size(); i++) {
        for (int j = n; j >= nums[i-1]; j--)
            dp[j] += dp[j-nums[i-1]];
    }
    return dp[n];
}

买卖股票之含手续费

给定一个整数数组 prices，其中 prices[i] 表示第 i 天的股票价格；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例 1：

输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8

示例 2：

输入：prices = [1,3,7,5,10,3], fee = 3
输出：6

第 i 天结束时，dp[i][0] 表示手里没有股票的最大利润，dp[i][1] 表示手里有股票的最大利润，则

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
int maxProfit(vector<int>& prices, int fee) {
    int n = prices.size();
    if (n == 1)
        return 0;
    vector<vector<int>> dp(n + 1, vector<int>(2));
    dp[1][0] = 0;
    dp[1][1] = -prices[0];
    for (int i = 2; i <= n; 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];
}

空间压缩大法：

1
2
3
4
5
6
7
8
9
10
11
int maxProfit(vector<int>& prices, int fee) {
    int n = prices.size();
    if (n == 1)
        return 0;
    int sell = 0, buy = -prices[0];
    for (int i = 2; i <= n; i++) {
        sell = max(sell, buy + prices[i-1] - fee);
        buy = max(buy, sell - prices[i-1]);
    }
    return sell;
}