LeetCode刷题笔记(六): 动态规划
算法介绍：动态规划(Dynamic Programming, DP)在查找有很多重叠子问题的情况的最优解时有效。它将问题重新组合成子问题。为了避免多次解决这些子问题，它们的结果都逐渐被计算并被保存，从简单的问题直到整个问题都被解决。因此，动态规划保存递归时的结果，因而不会在解决同样的问题时花费时间。
补充：
- 动态规划只能应用于有最优子结构的问题。最优子结构的意思是局部最优解能决定全局最优解(对有些问题这个要求并不能完全满足，故有时需要引入一定的近似)。简单地说，问题能够分解成子问题来解决。
- 动态规划和其它遍历算法(如深/广度优先搜索)都是将原问题拆成多个子问题然后求解，他们之间最本质的区别是，动态规划保存子问题的解，避免重复计算。解决动态规划问题的关键是找到状态转移方程，这样我们可以通过计算和储存子问题的解来求解最终问题。
- 可以对动态规划进行空间压缩，起到节省空间消耗的效果。
- 如果题目需求的是最终状态，那么使用动态搜索比较方便；如果题目需要输出所有的路径，那么使用带有状态记录的优先搜索会比较方便。
一、一维动态规划
题目一：爬楼梯
给定n节台阶，每次可以走一步或走两步，求一共有多少种方式可以走完这些台阶。解答：
1
2
3
4
5
6
7
8
9
10class Solution {
public:
int climbStairs(int n) {
vector<int> dp(n + 1, 1);
for (int i = 2; 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
12
13class Solution {
public:
int climbStairs(int n) {
if (n == 1) return 1;
int prevPrev = 1, prev = 1, cur = 0;
for (int i = 2; i <= n; ++i) {
cur = prevPrev + prev;
prevPrev = prev;
prev = cur;
}
return cur;
}
};补充：典型的斐波拉契数列问题，可转化为dp[n]=dp[n-1]+dp[n-2]。
题目二：打家劫舍
假如你是一个劫匪，并且决定抢劫一条街上的房子，每个房子内的钱财数量各不相同。如果你抢了两栋相邻的房子，则会触发警报机关。求在不触发机关的情况下最多可以抢劫多少钱。解答：
1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public:
int rob(vector<int>& nums) {
int prevPrev = 0, prev = 0, cur = 0;
for (int i = 0; i < nums.size(); ++i) {
cur = max(prevPrev + nums[i], prev);
prevPrev = prev;
prev = cur;
}
return cur;
}
};提示：状态转移方程为dp[n]=max(dp[n-1], dp[n-2]+nums[n])。
题目三：等差数列划分
如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。例如，[1,3,5,7,9]、[7,7,7,7]和[3,-1,-5,-9]都是等差数列。
给你一个整数数组nums，返回数组nums中所有为等差数组的子数组个数。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
int n = nums.size();
int count = 0, k = 0;
for (int i = 2; i < n; ++i) {
if (nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2]) {
++k;
count += k;
} else k = 0;
}
return count;
}
};提示：状态转移方程为dp[n]=dp[n-1]+1。
二、二维动态规划
题目一：最小路径和
给定一个包含非负整数的mxn网格grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
if (m == 1 && n == 1) return grid[0][0];
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) {
int minTrace = min(dp[i - 1][j], dp[i][j - 1]);
dp[i][j] = grid[i][j] + minTrace;
}
}
return dp[m - 1][n - 1];
}
};提示：状态转移方程为dp[i][j]=grid[i][j]+min(dp[i-1][j], dp[i][j-1])
题目二：01矩阵
给定一个由0和1组成的矩阵mat，请输出一个大小相同的矩阵，其中每一个格子是mat中对应位置元素到最近的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
25class Solution {
public:
vector<vector<int>> updateMatrix(vector<vector<int>> &matrix) {
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> dp(m, vector<int>(n, numeric_limits<int>::max() - 1));
for (int i = 0; i < m; ++i) {
for (int j = 0; j < n; ++j) {
if (matrix[i][j] != 0) {
if (i > 0) dp[i][j] = min(dp[i][j], dp[i - 1][j] + 1);
if (j > 0) dp[i][j] = min(dp[i][j], dp[i][j - 1] + 1);
}
else dp[i][j] = 0;
}
}
for (int i = m - 1; i >= 0; --i) {
for (int j = n - 1; j >= 0; --j) {
if (matrix[i][j] != 0) {
if (i < m - 1) dp[i][j] = min(dp[i][j], dp[i + 1][j] + 1);
if (j < n - 1) dp[i][j] = min(dp[i][j], dp[i][j + 1] + 1);
}
}
}
return dp;
}
};提示：需要左上到右下，右下到左上各扫一遍。
题目三：最大正方形
在一个由’0’和’1’组成的二维矩阵内，找到只包含’1’的最大正方形，并返回其面积。
解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int maxSide = 0;
int m = matrix.size(), n = matrix[0].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 (matrix[i - 1][j - 1] == '1') {
int minNum = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
dp[i][j] = minNum + 1;
}
maxSide = max(maxSide, dp[i][j]);
}
}
return maxSide * maxSide;
}
};提示：在右下角记录正方形的最大边，状态转移方程为dp[i][j]=1+min({dp[i-1][j-1], dp[i-1][j], dp[i][j-1]})。
三、分割问题
题目一：完全平方数
给你一个整数n，返回和为n的完全平方数的最少数量。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public:
int numSquares(int n) {
vector<int> dp(n + 1, 0);
for (int i = 1; i <= n; ++i) {
int minNum = 10001;
for (int j = 1; j * j <= i; ++j) {
minNum = min(minNum, dp[i - j * j]);
}
dp[i] = minNum + 1;
}
return dp[n];
}
};提示：位置只依赖于i-j^2，因为这样才符合完全平方数分割。
题目二：解码方法
已知字母 A-Z 可以表示成数字 1-26。给定一个数字串，求有多少种不同的字符串等价于这个数字串。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24class Solution {
public:
int numDecodings(string s) {
if (s[0] == '0') return 0;
int n = s.length();
if (n == 1) return 1;
vector<int> dp(n, 1);
if (s[0] == '1' || s[0] == '2' && s[1] <= '6') ++dp[1];
if (s[1] == '0') dp[1]--;
for (int i = 2; i < n; ++i) {
if (s[i] == '0') {
if (s[i - 1] > '2' || s[i - 1] == '0')
return 0;
else dp[i] = dp[i - 2];
}
else {
if (s[i - 1] == '1' || s[i - 1] == '2' && s[i] <= '6')
dp[i] = dp[i - 1] + dp[i - 2];
else dp[i] = dp[i - 1];
}
}
return dp[n - 1];
}
};提示：注意状态转移方程不止一种。
题目三：单词拆分
给你一个字符串s和一个字符串列表wordDict作为字典。如果可以利用字典中出现的一个或多个单词(可以重复使用)拼接出s则返回true。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
int size = s.length();
vector<bool> dp(size + 1, false);
dp[0] = true;
for (int i = 1; i <= size; ++i) {
for (const string& word : wordDict) {
int length = word.length();
if (i >= length && s.substr(i - length, length) == word)
dp[i] = dp[i - length];
if (dp[i]) break;
}
}
return dp[size];
}
};提示：和完全平方数差不多，位置只依赖于i-word.length。
题目四：填充书架
给定一个数组，每个元素代表一本书的厚度和高度。问对于一个固定宽度的书架，如果按照数组中书的顺序从左到右、从上到下摆放，最小总高度是多少。
解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
int minHeightShelves(vector<vector<int>>& books, int shelfWidth) {
int n = books.size();
vector<int> dp(n + 1, 0);
for (int i = 1; i <= n; ++i) {
int w = books[i - 1][0], h = books[i - 1][1];
dp[i] = dp[i - 1] + h;
for (int j = i - 1; j > 0; --j) {
int prevW = books[j - 1][0], prevH = books[j - 1][1];
w += prevW;
if (w > shelfWidth) break;
h = max(prevH, h);
dp[i] = min(dp[i], h + dp[j - 1]);
}
}
return dp[n];
}
};提示：摆放只有两种情况，摆在前一本书后面或者直接摆在下一层。
题目五：组合总和 Ⅳ
给定一个不重复数字的数组和一个目标数，求加起来是目标数的所有排列的总数量。(虽然这道题叫做Combination Sum，但是不同顺序的组合会被当作不同答案，因此本质上是排列)解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target + 1, 0);
dp[0] = 1;
for (int i = 1; i <= target; ++i) {
for (int num : nums) {
if (num <= i) {
if (dp[i] > __INT_MAX__ - dp[i - num]) break;
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
};提示：和完全平方数也是差不多的，这里为了全用int来完成时间上会稍稍多一点，可以换成double类型去掉多的if判断。
四、子序列问题
题目一：最长递增子序列
给你一个整数数组nums，找到其中最长严格递增子序列的长度。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n, 0);
int res = 1;
for (int i = 0; i < n; ++i) {
int maxTemp = 0;
for (int j = i; j >= 0; --j) {
if (nums[i] > nums[j])
maxTemp = max(maxTemp, dp[j]);
}
dp[i] = maxTemp + 1;
res = max(dp[i], res);
}
return res;
}
};提示：这道题很简单，但是动态规划并不是最优解。
题目二：最长公共子序列
给定两个字符串text1和text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列，返回0。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
int len1 = text1.length();
int len2 = text2.length();
vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));
for (int i = 1; i <= len1; ++i) {
for (int j = 1; j <= len2; ++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[len1][len2];
}
};提示：使用二维dp来记录，dp[i][j]记录的是text1.length<=1，text2.length<=j时最大的公共子长度。
五、背包问题
算法解释：背包问题(knapsack problem)是一种组合优化的NP完全问题：有n个物品和载重为w的背包，每个物品都有自己的重量weight和价值value，求拿哪些物品可以使得背包所装下物品的总价值最大。如果限定每种物品只能选择0个或1个，则问题称为0-1背包问题(0-1 knapsack)；如果不限定每种物品的数量，则问题称为无界背包问题或完全背包问题(unbounded knapsack)。我们可以用动态规划来解决背包问题。以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件物品重量为weight，价值为value，那么我们得到dp[i][j]=dp[i-1][j-weight]+value。我们只需在遍历过程中对这两种情况取最大值即可，总时间复杂度和空间复杂度都为O(nw)。
- 状态转移矩阵示例：
- 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14int 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 weight = weights[i - 1], value = values[i - 1];
for (int j = 1; j <= w; ++j) {
if (j >= weight) {
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight] + value);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][w];
} - 代码2(空间复杂度为O(w))：
1
2
3
4
5
6
7
8
9
10int 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 weight = weights[i - 1], value = values[i - 1];
for (int j = w; j >= weight; --j) {
dp[j] = max(dp[j], dp[j - weight] + value);
}
}
return dp[w];
}
无界背包问题
- 分析：在完全背包问题中，一个物品可以拿多次。如图上半部分所示，假设我们遍历到物品i=2，且其重量为weight=2，价值为value=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
14int 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 weight = weights[i - 1], value = values[i - 1];
for (int j = 1; j <= w; ++j) {
if (j >= weight) {
dp[i][j] = max(dp[i - 1][j], dp[i][j - weight] + value);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][w];
} - 代码2(空间复杂度为O(w))：
1
2
3
4
5
6
7
8
9
10int 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 weight = weights[i - 1], value = values[i - 1];
for (int j = weight; j <= w; ++j) {
dp[j] = max(dp[j], dp[j - weight] + value);
}
}
return dp[w];
}
题目一：分割等和子集
给你一个只包含正整数的非空数组nums。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
bool canPartition(vector<int>& nums) {
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % 2 == 1) return false;
int n = nums.size();
int target = sum / 2;
vector<int> dp(target + 1, 0);
for (int i = 1; i <= n; ++i) {
int weight = nums[i - 1];
for (int j = target; j >= weight; --j) {
dp[j] = max(dp[j], dp[j - weight] + weight);
}
}
return dp[target] == target;
}
};提示：注意这道题没有value且要知道背包的容量为sum/2。
题目二：一和零
给定m个数字0和n个数字1，以及一些由0-1构成的字符串，求利用这些数字最多可以构成多少个给定的字符串，字符串只可以构成一次。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
int len = strs.size();
vector<int> weights0(len, 0);
vector<int> weights1(len, 0);
for (int i = 0; i < len; ++i) {
for (char c : strs[i]) {
if (c == '0') ++weights0[i];
else ++weights1[i];
}
}
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 0; i < len; ++i) {
for (int j = m; j >= weights0[i]; --j) {
for (int k = n; k >= weights1[i]; --k) {
dp[j][k] = max(dp[j][k], dp[j - weights0[i]][k - weights1[i]] + 1);
}
}
}
return dp[m][n];
}
};提示：本质上是一个双重背包。
题目三：零钱交换
给定一些硬币的面额，求最少可以用多少颗硬币组成给定的金额，硬币可以重复使用。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, 10001);
dp[0] = 0;
for (int i = 0; i < coins.size(); ++i) {
for (int j = coins[i]; j <= amount; ++j) {
dp[j] = min(dp[j], dp[j - coins[i]] + 1);
}
}
return dp[amount] == 10001 ? -1 : dp[amount];
}
};提示：很典型的无限背包问题。
六、股票问题
题目一：买卖股票的最佳时机
给定一段时间内每天某只股票的固定价格，已知你只可以买卖各一次，求最大的收益。解答：
1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public:
int maxProfit(vector<int>& prices) {
int res = 0;
int minSale = prices[0];
for (int i = 1; i < prices.size(); ++i) {
if (prices[i] < minSale) minSale = prices[i];
else res = max(res, prices[i] - minSale);
}
return res;
}
};提示：简单题，使用贪心思想即可。
题目二：买卖股票的最佳时机 IV
给定一段时间内每天某只股票的固定价格，已知你只可以买卖各k次，且每次只能拥有一支股票，求最大的收益。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
vector<int> buy(k + 1, -1001), sell(k + 1, 0);
for (int i = 0; i < prices.size(); ++i) {
for (int j = 1; j <= k; ++j) {
buy[j] = max(buy[j], sell[j - 1] - prices[i]);
sell[j] = max(sell[j], buy[j] + prices[i]);
}
}
return sell[k];
}
};提示：需要用两个数组来维护状态，思考一下状态转换的关系。
题目三：买卖股票的最佳时机含冷冻期
给定一段时间内每天某只股票的固定价格，已知每次卖出之后必须冷却一天，且每次只能拥有一支股票，求最大的收益。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
int maxProfit(vector<int> &prices) {
int n = prices.size();
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]);
}
};提示：考虑如下状态转换图，这道题还有二维dp的做法，二维dp的做法也可以被压缩成一维dp的做法。
七、练习
题目一：打家劫舍 II
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
int prev = 0, pevPrev = 0, cur1 = 0;
for (int i = 0; i < n - 1; ++i) {
cur1 = max(pevPrev + nums[i], prev);
pevPrev = prev;
prev = cur1;
}
prev = 0, pevPrev = 0;
int cur2 = 0;
for (int i = 1; i < n; ++i) {
cur2 = max(pevPrev + nums[i], prev);
pevPrev = prev;
prev = cur2;
}
return max(cur1, cur2);
}
};提示：处理一下首尾，分开算一遍即可。
题目二：最大子数组和
给你一个整数数组nums，请你找出一个具有最大和的连续子数组(子数组最少包含一个元素)，返回其最大和。解答：
1
2
3
4
5
6
7
8
9
10
11class Solution {
public int maxSubArray(int[] nums) {
int res = nums[0];
int pre = nums[0];
for (int i = 1; i < nums.length; i ++) {
pre = Math.max(pre + nums[i], nums[i]);
res = Math.max(pre, res);
}
return res;
}
}提示：要么加入当前的，要么重新从当前的重新开始。
题目三：整数拆分
给定一个正整数n，将其拆分为k个正整数的和(k>=2)，并使这些整数的乘积最大化。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
int integerBreak(int n) {
if (n <= 3) return n - 1;
vector<int> dp(n + 1, 1);
for (int i = 1; i <= n; ++i) {
dp[i] = i;
}
for (int i = 4; i <= n; ++i) {
for (int j = 2; j < i; ++j) {
dp[i] = max(dp[i], j * dp[i - j]);
}
}
return dp[n];
}
};提示：分割类型的问题。
题目四：两个字符串的删除操作
给定两个单词word1和word2，返回使得word1和word2相同所需的最小步数。每步可以删除任意一个字符串中的一个字符。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
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 = 1; i <= m; ++i) {
dp[i][0] = i;
for (int j = 1; j <= n; ++j) {
dp[0][j] = 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];
}
};提示：最长公共子序列的变种题，注意i和j为0时的赋值。
题目五：正则表达式匹配
给你一个字符串s和一个字符规律p，请你来实现一个支持’.’和’*’的正则表达式匹配。- ‘.’匹配任意单个字符。
- ‘*’匹配零个或多个前面的那一个元素。
解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public:
bool isMatch(string s, string p) {
int m = s.length(), n = p.length();
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
dp[0][0] = true;
for (int i = 0; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p[j - 1] == '*') {
dp[i][j] = dp[i][j] || dp[i][j - 2];
if (i > 0 && (p[j - 2] == s[i - 1] || p[j - 2] == '.'))
dp[i][j] = dp[i][j] || dp[i - 1][j];
} else {
if (i > 0 && (p[j - 1] == s[i - 1] || p[j - 1] == '.')) {
dp[i][j] = dp[i][j] || dp[i - 1][j - 1];
}
}
}
}
return dp[m][n];
}
};提示：非常麻烦的题，i=0是为了处理p的开头两个就有’*‘的情况，而当p[j]=’*‘时，本质上只会有两种情况：匹配s末尾的一个字符，将该字符扔掉，而该组合还可以继续进行匹配；不匹配字符，将该组合扔掉，不再进行匹配。如果仍然不太理解的话，可以考虑用for循环处理。
题目六：目标和
给你一个非负整数数组nums和一个整数target。向数组中的每个整数前添加’+’或’-‘，然后串联起所有整数，可以构造一个表达式(例如’+2-1’)。
返回可以通过上述方法构造的、运算结果等于target的不同表达式的数目。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution {
public:
int findTargetSumWays(vector<int>& nums, int target) {
int sum = accumulate(nums.begin(), nums.end(), 0);
int diff = sum - target;
if (diff < 0 || diff % 2 != 0) return 0;
int neg = (sum - target) / 2;
vector<int> dp(neg + 1, 0);
dp[0] = 1;
for (int i = 0; i < nums.size(); ++i) {
for (int j = neg; j >= nums[i]; --j) {
dp[j] = dp[j] + dp[j - nums[i]];
}
}
return dp[neg];
}
};提示：本质上是一个0-1背包问题，设有neg个数字取负，则有sum-neg-neg=target，剩下的就是选取元素之和为neg的元素排列个数了。
题目七：买卖股票的最佳时机含手续费
给定一个整数数组prices，其中prices[i]表示第i天的股票价格；整数fee代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。解答：
1
2
3
4
5
6
7
8
9
10
11
12
13
14class Solution {
public:
int maxProfit(vector<int> &prices, int fee) {
int n = prices.size();
vector<int> dp(3);
dp[0] = 0, dp[1] = -prices[0], dp[2] = 0;
for (int i = 1; i < n; ++i) {
dp[0] = max(dp[0], dp[2]);
dp[1] = max(dp[1], max(dp[0] - prices[i], dp[2] - prices[i]));
dp[2] = max(dp[2], dp[1] + prices[i] - fee);
}
return max(dp[0], dp[2]);
}
};提示：三个状态：未持有股票未售卖；持有股票；持有股票刚售卖。
相关推荐
2025-08-25
LeetCode刷题笔记(一): 贪心
贪心算法的核心思想：局部最优以实现全局最优。 一、分配问题 题目：分发糖果n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。你需要按照以下要求，给这些孩子分发糖果： 每个孩子至少分配到 1 个糖果。 相邻两个孩子中，评分更高的那个会获得更多的糖果。请你给每个孩子分发糖果，计算并返回需要准备的最少糖果数目。 解答： 123456789101112131415161718class Solution {public: int candy(vector<int> &ratings) { int n = ratings.size(); vector<int> candies(n, 1); for (int i = 1; i < n; ++i) { if (ratings[i] > ratings[i - 1]) { candies[i] = candies[i - 1] +...
2025-09-21
LeetCode刷题笔记(九): 位运算
常用技巧(其中0s和1s分别表示只由0或1构成的二进制数字。)：123x ^ 0s = x x & 0s = 0 x | 0s = xx ^ 1s = ~x x & 1s = x x | 1s = 1sx ^ x = 0 x & x = x x | x = x 除此之外，n&(n-1)可以去除n的位级表示中最低的那一位，例如对于二进制表示11110100，减去1得到11110011，这两个数按位与得到11110000。n&(-n)可以得到n的位级表示中最低的那一位，例如对于二进制表示11110100，取负得到00001100，这两个数按位与得到00000100。 一、位运算基础问题 题目一：汉明距离给定两个十进制数字，求它们二进制表示的汉明距离(Hamming distance，即不同位的个数)。 解答： 12345678910111213class Solution {public: int hammingDistance(int x, int y)...
2025-08-26
LeetCode刷题笔记(二): 双指针
双指针算法的核心思想：双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。也可以延伸到多个数组的多个指针。 一、Two Sum 题目：两数之和 II - 输入有序数组给你一个下标从1开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。 解答： 12345678910vector<int> twoSum(vector<int>& numbers, int target) { int l = 0, r = numbers.size() - 1, two_sum; while (l < r) { ...
2025-08-27
LeetCode刷题笔记(三): 二分查找
二分查找算法的核心思想：二分查找也常被称为二分法或者折半查找 (binary search, bisect)，每次查找时通过将待查找的单调区间分成两部分并只取一部分继续查找，将查找的复杂度大大减少。对于一个长度为O(n)的数组，二分查找的时间复杂度为O(logn)。 一、求开方 题目：x 的平方根给定一个非负整数 x，求它的开方，向下取整。 解答： 12345678910111213141516int mySqrt(int x) { int l = 1, r = x, mid, x_div_mid; while (l <= r) { mid = l + (r - l) / 2; x_div_mid = x / mid; if (mid == x_div_mid) { return mid; } if (mid < x_div_mid) { l = mid + 1; }...
2025-09-15
LeetCode刷题笔记(七): 数学问题
一、最大公约数和最小公倍数这个没什么好说的，辗转相除法： 1234567int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }int lcm(int a, int b) { return a * b / gcd(a, b); } 也可以通过扩展欧几里得算法(extended gcd)在求得a和b最大公因数的同时，也得到它们的系数x和y，从而使ax+by=gcd(a, b)，也就是贝祖等式。 12345678910int xGCD(int a, int b, int &x, int &y) { if (b == 0) { x = 1, y = 0; return a; } int x_inner, y_inner; int gcd = xGCD(b, a % b, x_inner, y_inner); x = y_inner, y =...
2025-08-28
LeetCode刷题笔记(四): 排序
排序算法：包括快排，归并排序，桶排序，哈希排序等。 一、快排 算法介绍：对于当前一个未排序片段，我们先随机选择一个位置当作中枢点，然后通过遍历操作，将所有比中枢点小的数字移动到其左侧，再将所有比中枢点大的数字移动到其右侧。操作完成后，我们再次对中枢点左右侧的片段再次进行快速排序即可。可证明，如果中枢点选取是随机的，那么该算法的平均复杂度可以达到O(nlogn)，最差情况下复杂度则为O(n^2)。 代码： 1234567891011121314151617void quickSort(vector<int> &nums, int l, int r) { if (l >= r) return; int pivot = l + (rand() % (r - l + 1)); int pivot_val = nums[pivot]; swap(nums[l], nums[pivot]); int i = l + 1, j = r; while (true) { while (i < j &&...
评论
