A summary of dynamic programming related problems from LeetCode with solutions in C++.
Problems:
509. Fibonacci Number
70. Climbing Stairs
746. Min Cost Climbing Stairs
62. Unique Paths
63. Unique Paths II
343. Integer Break
96. Unique Binary Search Trees
416. Partition Equal Subset Sum
1049. Last Stone Weight II
494. Target Sum
474. Ones and Zeroes
518. Coin Change II
377. Combination Sum IV
70. Climbing Stairs
322. Coin Change
279. Perfect Squares
139. Word Break
198. House Robber
213. House Robber II
337. House Robber III
121. Best Time to Buy and Sell Stock
122. Best Time to Buy and Sell Stock II
123. Best Time to Buy and Sell Stock III
188. Best Time to Buy and Sell Stock IV
309. Best Time to Buy and Sell Stock with Cooldown
714. Best Time to Buy and Sell Stock with Transaction Fee
300. Longest Increasing Subsequence
674. Longest Continuous Increasing Subsequence
718. Maximum Length of Repeated Subarray
1143. Longest Common Subsequence
1035. Uncrossed Lines
53. Maximum Subarray
392. Is Subsequence
115. Distinct Subsequences
583. Delete Operation for Two Strings
72. Edit Distance
647. Palindromic Substrings
516. Longest Palindromic Subsequence
Problem : The Fibonacci numbers , commonly denoted F(n) form a sequence, called the Fibonacci sequence , such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,
F(0) = 0, F(1) = 1
F(n) = F(n – 1) + F(n – 2), for n > 1.
Given n, calculate F(n).
Case 1: Input: n = 2, Output: 1
Case 2: Input: n = 3, Output: 2
Case 2: Input: n = 4, Output: 3
class Solution {
public:
// 时间复杂度: O(n)
// 空间复杂度: O(n)
int fib(int N) {
if (N <= 1) { return N;}
vector<int> dp(N + 1);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= N; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[N];
}
};
class Solution {
public:
// 时间复杂度: O(n)
// 空间复杂度: O(1)
int fib(int N) {
if (N <= 1) { return N; }
int dp[2];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= N; i++) {
int sum = dp[0] + dp[1];
dp[0] = dp[1];
dp[1] = sum;
}
return dp[1];
}
};
class Solution {
public:
// 时间复杂度: O(2^n)
// 空间复杂度: O(n)
int fib(int N) {
if (N < 2) { return N; }
return fib(N - 1) + fib(N - 2);
}
};
Problem: You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top
Case 1: Input: n = 2, Output: 2
Case 2: Input: n = 3, Output: 3
递推公式dp[i] = dp[i – 1] + dp[i – 2]
class Solution {
public:
// 时间复杂度: O(n)
// 空间复杂度: O(1)
int climbStairs(int n) {
if (n <= 1) { return n; }
int dp[3];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
int sum = dp[1] + dp[2];
dp[1] = dp[2];
dp[2] = sum;
}
return dp[2];
}
};
3. 746. Min Cost Climbing Stairs
Problem: You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps. You can either start from the step with index 0, or the step with index 1. Return the minimum cost to reach the top of the floor.
Case 1: Input: cost = [10,15,20], Output: 15
Case 2: Input: cost = [1,100,1,1,1,100,1,1,100,1], Output: 15
dp[i]的定义: 到达第i台阶所花费的最少体力为dp[i]
dp[i-1] 跳到 dp[i] 需要花费 dp[i-1] + cost[i-1]
dp[i-2] 跳到 dp[i] 需要花费 dp[i-2] + cost[i-2]
dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])
初始化 dp[0] = 0, dp[1] = 0
class Solution {
public:
// 时间复杂度: O(n)
// 空间复杂度: O(1)
int minCostClimbingStairs(vector<int>& cost) {
int dp0 = 0;
int dp1 = 0;
for (int i = 2; i <= cost.size(); i++) {
int dpi = min(dp1 + cost[i - 1], dp0 + cost[i - 2]);
dp0 = dp1; // 记录一下前两位
dp1 = dpi;
}
return dp1;
}
};
Problem: There is a robot on an m x n grid. The robot is initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m – 1][n – 1]). The robot can only move either down or right at any point in time. Given the two integers m and n, return the number of possible unique paths that the robot can take to reach the bottom-right corner. The test cases are generated so that the answer will be less than or equal to 2 * 109.
Case 1: Input: m = 3, n = 7, Output: 28
Case 2: Input: m = 3, n = 2, Output: 3
(1) 确定dp数组(dp table)以及下标的含义
dp[i][j]: 表示从(0, 0)出发到(i, j)有dp[i][j]条不同的路径
(2) 确定递推公式
dp[i][j] = dp[i-1][j] + dp[i][j-1], 因为dp[i][j]只有这两个方向过来
(3) dp数组的初始化
首先dp[i][0]一定都是1, 因为从(0, 0)的位置到(i, 0)的路径只有一条, 那么dp[0][j]也同理
(4) 确定遍历顺序
dp[i][j]都是从其上方和左方推导而来, 那么从左到右一层一层遍历就可以了, 可以保证推导dp[i][j]的时候, dp[i-1][j]和dp[i][j-1]一定是有数值的
(5) 举例推导dp数组
class Solution {
public:
// 时间复杂度: O(m × n)
// 空间复杂度: O(m × n)
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m, vector<int>(n, 0));
for (int i = 0; i < m; i++) {dp[i][0] = 1;} // 初始化第一横行
for (int j = 0; j < n; j++) {dp[0][j] = 1;} // 初始化第一竖列
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
};
Problem: You are given an m x n integer array grid. There is a robot initially located at the top-left corner (i.e., grid[0][0]). The robot tries to move to the bottom-right corner (i.e., grid[m – 1][n – 1]). The robot can only move either down or right at any point in time. An obstacle and space are marked as 1 or 0 respectively in grid. A path that the robot takes cannot include any square that is an obstacle. Return the number of possible unique paths that the robot can take to reach the bottom-right corner. The testcases are generated so that the answer will be less than or equal to 2 * 109.
Case 1: Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]], Output: 2
Case 2: Input: obstacleGrid = [[0,1],[0,0]], Output: 1
(1) 确定dp数组(dp table)以及下标的含义
dp[i][j]: 表示从(0, 0)出发到(i, j)有dp[i][j]条不同的路径
(2) 确定递推公式
dp[i][j] = dp[i-1][j] + dp[i][j-1], 因为dp[i][j]只有这两个方向过来
因为有了障碍(i, j)如果就是障碍的话应该就保持初始状态0
(3) dp数组如何初始化
因为从(0, 0)的位置到(i, 0)的路径只有一条, 所以dp[i][0]一定为1, dp[0][j]也同理。但如果(i, 0)这条边有了障碍之后, 障碍之后(包括障碍)都是走不到的位置了, 所以障碍之后的dp[i][0]应该还是初始值0
(4) 确定遍历顺序
从递归公式dp[i][j] = dp[i-1][j] + dp[i][j-1]中可以看出, 一定是从左到右一层一层遍历, 这样保证推导dp[i][j]的时候, dp[i-1][j]和dp[i][j-1]一定是有数值
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
//如果在起点或终点出现了障碍, 直接返回0
if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) {return 0;}
vector<vector<int>> dp(m, vector<int>(n, 0));
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) { dp[i][0] = 1; }
for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) { dp[0][j] = 1; }
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (obstacleGrid[i][j] == 1) { continue; }
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
};
Problem: Given an integer n, break it into the sum of k positive integers, where k >= 2, and maximize the product of those integers. Return the maximum product you can get.
Case 1: Input: n = 2, Output: 1, Explanation: 2 = 1 + 1, 1 × 1 = 1
Case 2: Input: n = 10, Output: 36, Explanation: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
(1) dp[i]: 分拆数字i, 可以得到的最大乘积为dp[i]
(2) 确定递推公式: 一个是j * (i – j)直接相乘, 一个是j * dp[i – j]，相当于是拆分(i – j)。 j * (i – j)是单纯的把整数拆分为两个数相乘, 而j * dp[i – j]是拆分成两个以及两个以上的个数相乘。
从1遍历j, 比较(i – j) * j和dp[i – j] * j取最大的。
递推公式: dp[i] = max(dp[i], max((i – j) * j, dp[i – j] * j))
(3) dp的初始化: 严格从dp[i]的定义来说, dp[0]和dp[1]就不应该初始化, 也就是没有意义的数值, 初始化dp[2] = 1
(4) 确定遍历顺序: dp[i]是依靠 dp[i – j]的状态, 所以遍历i一定是从前向后遍历, 先有dp[i – j]再有dp[i]
(5) 举例当n为10 的时候, dp数组里的数值, 如下
class Solution {
public:
// 时间复杂度: O(n^2)
// 空间复杂度: O(n)
int integerBreak(int n) {
vector<int> dp(n + 1);
// dp[0], dp[1] makes no sense
dp[2] = 1;
for (int i = 3; i <= n ; i++) {
for (int j = 1; j <= i / 2; j++) {
dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
}
}
return dp[n];
}
};
7. 96. Unique Binary Search Trees
Problem: Given an integer n, return the number of structurally unique BST‘s (binary search trees) which has exactly n nodes of unique values from 1 to n.
Case 1: Input: n = 3, Output: 5
Case 2: Input: n = 1, Output: 1
n为1的时候有一棵树, n为2有两棵树
看看n为3的时候, 有哪几种情况
(1) 当1为头结点的时候, 其右子树有两个节点, 这两个节点的布局和n为2的时候两棵树的布局是一样的
(2) 当3为头结点的时候, 其左子树有两个节点, 这两个节点的布局和n为2的时候两棵树的布局也是一样的
(3) 当2为头结点的时候, 其左右子树都只有一个节点, 布局和n为1的时候只有一棵树的布局是一样的
(4) 可以通过dp[1]和dp[2]来推导出来dp[3]
dp[3] = 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
有2个元素的搜索树数量就是dp[2]
有1个元素的搜索树数量就是dp[1]
有0个元素的搜索树数量就是dp[0]
所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
如图所示:
(1) dp[i]: 1到i为节点组成的二叉搜索树的个数为dp[i], 也可以理解是i个不同元素节点组成的二叉搜索树的个数为dp[i]
(2) 确定递推公式: dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]
j相当于是头结点的元素, 从1遍历到i为止
递推公式: dp[i] += dp[j – 1] * dp[i – j]
j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量
(3) dp数组如何初始化: dp[0] = 1
(4) 确定遍历顺序: 首先一定是遍历节点数, 从递归公式: dp[i] += dp[j – 1] * dp[i – j]可以看出, 节点数为i的状态是依靠i之前节点数的状态。那么遍历i里面每一个数作为头结点的状态, 用j来遍历。
(5) 举例推导dp数组: n为5时候的dp数组状态如图
class Solution {
public:
// 时间复杂度: O(n^2)
// 空间复杂度: O(n)
int numTrees(int n) {
vector<int> dp(n + 1);
dp[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
};
8. 416. Partition Equal Subset Sum
Problem: Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.
Case 1: Input: nums = [1,5,11,5], Output: true
Case 2: Input: nums = [1,2,3,5], Output: false
背包问题: 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i], 得到的价值是value[i]。每件物品只能用一次, 求解将哪些物品装入背包里物品价值总和最大。一个商品如果可以重复多次放入是完全背包, 而只能放入一次是01背包。
确定了如下四点, 才能把01背包问题套到本题上
(1) 背包的体积为sum/2
(2) 背包要放入的商品(集合里的元素)重量为元素的数值, 价值也为元素的数值
(3) 背包如果正好装满, 说明找到了总和为sum/2的子集
(4) 背包中每一个元素是不可重复放入
(1) 确定dp数组以及下标的含义: 01背包中, dp[j]表示容量为j的背包, 所背的物品价值最大可以为dp[j]
(2) 确定递推公式: 01背包的递推公式为: dp[j] = max(dp[j], dp[j – weight[i]] + value[i]); 本题相当于背包里放入数值, 那么物品i的重量是nums[i], 其价值也是nums[i]。递推公式: dp[j] = max(dp[j], dp[j – nums[i]] + nums[i]);
(3) dp数组如何初始化: 从dp[j]的定义来看, 首先dp[0]一定是0。如果题目给的价值都是正整数那么非0下标都初始化为0就可以了, 如果题目给的价值有负数, 那么非0下标就要初始化为负无穷。
(4) 确定遍历顺序: 如果使用一维dp数组, 物品遍历的for循环放在外层, 遍历背包的for循环放在内层, 且内层for循环倒序遍历
(5) 举例推导dp数组: dp[j]的数值一定是小于等于j的
如果dp[j] == j 说明, 集合中的子集总和正好可以凑成总和j
用例1, 输入[1,5,11,5]为例, 如图
最后dp[11] == 11, 说明可以将这个数组分割成两个子集, 使得两个子集的元素和相等
class Solution {
public:
// 时间复杂度: O(n^2)
// 空间复杂度: O(n)
bool canPartition(vector<int>& nums) {
// dp[i]中的i表示背包内总和
// 题目中说: 每个数组中的元素不会超过 100, 数组的大小不会超过200
// 总和不会大于20000, 背包最大只需要其中一半, 所以10001大小就可以了
vector<int> dp(10001, 0);
int sum = 0;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
}
// 也可以使用库函数一步求和
// int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum % 2 == 1) { return false; }
int target = sum / 2;
// 开始01背包
for(int i = 0; i < nums.size(); i++) {
// 每一个元素一定是不可重复放入, 所以从大到小遍历
for(int j = target; j >= nums[i]; j--) {
dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
}
}
// 集合中的元素正好可以凑成总和target
if (dp[target] == target) { return true; }
return false;
}
};
Problem: You are given an array of integers stones where stones[i] is the weight of the ith stone. We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:
If x == y, both stones are destroyed, and
If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y – x.
At the end of the game, there is at most one stone left.
Return the smallest possible weight of the left stone. If there are no stones left, return 0.
Case 1: Input: stones = [2,7,4,1,8,1], Output: 1
Case 2: Input: stones = [31,26,33,21,40], Output: 5
(1) 确定dp数组以及下标的含义: dp[j]表示容量(这里说容量更形象, 其实就是重量)为j的背包, 最多可以背最大重量为dp[j], 本题中, 石头的重量是 stones[i], 石头的价值也是 stones[i], “最多可以装的价值为 dp[j]” == “最多可以背的重量为dp[j]”
(2) 确定递推公式: 01背包的递推公式为: dp[j] = max(dp[j], dp[j – weight[i]] + value[i]); 本题则是: dp[j] = max(dp[j], dp[j – stones[i]] + stones[i]);
(3) dp数组如何初始化: 既然 dp[j]中的j表示容量, 那么最大容量(重量)是多少呢, 就是所有石头的重量和, 我们要求的target其实只是最大重量的一半, 因为重量都不会是负数, 所以dp[j]都初始化为0就可以了
(4) 确定遍历顺序: 如果使用一维dp数组, 物品遍历的for循环放在外层, 遍历背包的for循环放在内层, 且内层for循环倒序遍历
(5) 举例推导dp数组: 举例, 输入: [2,4,1,1], 此时target = (2 + 4 + 1 + 1)/2 = 4, dp数组状态图如下
最后dp[target]里是容量为target的背包所能背的最大重量, 那么分成两堆石头, 一堆石头的总重量是dp[target], 另一堆就是sum – dp[target], 那么相撞之后剩下的最小石头重量就是 (sum – dp[target]) – dp[target]
class Solution {
public:
// m是石头总重量的一半, n为石头块数
// 时间复杂度: O(m × n)
// 空间复杂度: O(m)
int lastStoneWeightII(vector<int>& stones) {
vector<int> dp(15001, 0);
int sum = 0;
for (int i = 0; i < stones.size(); i++) { sum += stones[i]; }
int target = sum / 2;
for (int i = 0; i < stones.size(); i++) { // 遍历物品
for (int j = target; j >= stones[i]; j--) { // 遍历背包
dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
}
}
return sum - dp[target] - dp[target];
}
};
10. 494. Target Sum
Problem: You are given an integer array nums and an integer target. You want to build an expression out of nums by adding one of the symbols ‘+’ and ‘-‘ before each integer in nums and then concatenate all the integers. For example, if nums = [2, 1], you can add a ‘+’ before 2 and a ‘-‘ before 1 and concatenate them to build the expression “+2-1”. Return the number of different expressions that you can build, which evaluates to target.
Case 1: Input: nums = [1,1,1,1,1], target = 3, Output: 5
Case 2: Input: nums = [1], target = 1, Output: 1
假设加法的总和为x, 那么减法对应的总和就是sum – x, 所以我们要求的是 x – (sum – x) = target, x = (target + sum) / 2, 这里的x, 就是bagSize, 也就是背包容量
(1) 确定dp数组以及下标的含义: dp[j]表示: 填满j(包括j)这么大容积的包, 有dp[j]种方法
(2) 确定递推公式: 只要搞到nums[i], 凑成dp[j]就有dp[j – nums[i]]种方法
例如: dp[j], j为5
已经有一个1(nums[i])的话, 有dp[4]种方法凑成容量为5的背包
已经有一个2(nums[i])的话, 有dp[3]种方法凑成容量为5的背包
已经有一个3(nums[i])的话, 有dp[2]中方法凑成容量为5的背包
已经有一个4(nums[i])的话, 有dp[1]中方法凑成容量为5的背包
已经有一个5(nums[i])的话, 有dp[0]中方法凑成容量为5的背包
那么凑整dp[5]有多少方法呢, 也就是把所有的dp[j – nums[i]]累加起来
(3) dp数组如何初始化: dp[0]应该初始化为1, dp[j]其他下标对应的数值也应该初始化为0, 从递推公式也可以看出, dp[j]要保证是0的初始值, 才能正确的由dp[j – nums[i]]推导出来
(4) 确定遍历顺序: nums放在外循环, target在内循环, 且内循环倒序
(5) 举例推导dp数组: 输入: nums: [1, 1, 1, 1, 1], S: 3, bagSize = (S + sum) / 2 = (3 + 5) / 2 = 4, dp数组状态变化如下
class Solution {
public:
// 时间复杂度: O(n × m), n为正数个数, m为背包容量
// 空间复杂度: O(m), m为背包容量
int findTargetSumWays(vector<int>& nums, int target) {
int sum = 0;
for (int i = 0; i < nums.size(); i++) { sum += nums[i]; }
if (abs(target) > sum) { return 0; } // 此时没有方案
if ((target + sum) % 2 == 1) { return 0; } // 此时没有方案
int bagSize = (target + sum) / 2;
vector<int> dp(bagSize + 1, 0);
dp[0] = 1;
for (int i = 0; i < nums.size(); i++) {
for (int j = bagSize; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]];
}
}
return dp[bagSize];
}
};
Problem: You are given an array of binary strings strs and two integers m and n. Return the size of the largest subset of strs such that there are at most m 0’s and n 1’s in the subset. A set x is a subset of a set y if all elements of x are also elements of y.
Case 1: Input: strs = [“10″,”0001″,”111001″,”1″,”0”], m = 5, n = 3, Output: 4
Case 2: Input: strs = [“10″,”0″,”1”], m = 1, n = 1, Output: 2
本题中strs数组里的元素就是物品, 每个物品都是一个
(1) 确定dp数组以及下标的含义: dp[i][j]: 最多有i个0和j个1的strs的最大子集的大小为dp[i][j]
(2) 确定递推公式: dp[i][j]可以由前一个strs里的字符串推导出来, strs里的字符串有zeroNum个0, oneNum个1, dp[i][j]就可以是dp[i – zeroNum][j – oneNum] + 1, 递推公式: dp[i][j] = max(dp[i][j], dp[i – zeroNum][j – oneNum] + 1), 字符串的zeroNum和oneNum相当于物品的重量weight[i], 字符串本身的个数相当于物品的价值value[i]
(3) dp数组如何初始化: 因为物品价值不会是负数, 初始为0, 保证递推的时候dp[i][j]不会被初始值覆盖
(4) 确定遍历顺序: 物品就是strs里的字符串, 背包容量就是题目描述中的m和n
(5) 举例推导dp数组: 输入: [“10″,”0001″,”111001″,”1″,”0”], m = 3, n = 3为例
class Solution {
public:
int findMaxForm(vector<string>& strs, int m, int n) {
// 默认初始化0
vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0));
// 遍历物品
for (string str : strs) {
int oneNum = 0, zeroNum = 0;
for (char c : str) {
if (c == '0') { zeroNum++; }
else { oneNum++; }
}
// 遍历背包容量且从后向前遍历
for (int i = m; i >= zeroNum; i--) {
for (int j = n; j >= oneNum; j--) {
dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
}
}
}
return dp[m][n];
}
};
Problem: You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0. You may assume that you have an infinite number of each kind of coin. The answer is guaranteed to fit into a signed 32-bit integer.
Case 1: Input: amount = 5, coins = [1,2,5], Output: 4
Case 2: Input: amount = 3, coins = [2], Output: 0
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> dp(amount + 1, 0);
dp[0] = 1;
for (int i = 0; i < coins.size(); i++) { // 遍历物品
for (int j = coins[i]; j <= amount; j++) { // 遍历背包
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
};
Problem: Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target. The test cases are generated so that the answer can fit in a 32-bit integer.
Case 1: Input: nums = [1,2,3], target = 4, Output: 7
Case 2: Input: nums = [9], target = 3, Output: 0
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target + 1, 0);
dp[0] = 1;
for (int i = 0; i <= target; i++) { // 遍历背包
for (int j = 0; j < nums.size(); j++) { // 遍历物品
if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]) {
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}
};
Problem: You are climbing a staircase. It takes n steps to reach the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Case 1: Input: n = 2, Output: 2
Case 2: Input: n = 3, Output: 3
class Solution {
public:
int climbStairs(int n) {
vector<int> dp(n + 1, 0);
dp[0] = 1;
int m = 2;
for (int i = 1; i <= n; i++) { // 遍历背包
for (int j = 1; j <= m; j++) { // 遍历物品
if (i - j >= 0) { dp[i] += dp[i - j]; }
}
}
return dp[n];
}
};
15. 322. Coin Change
Problem: You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money. Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1. You may assume that you have an infinite number of each kind of coin.
Case 1: Input: coins = [1,2,5], amount = 11, Output: 3
Case 2: Input: coins = [2], amount = 3, Output: -1
Case 3: Input: coins = [1], amount = 0, Output: 0
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
vector<int> dp(amount + 1, INT_MAX);
dp[0] = 0;
for (int i = 0; i < coins.size(); i++) { // 遍历物品
for (int j = coins[i]; j <= amount; j++) { // 遍历背包
// 如果dp[j - coins[i]]是初始值则跳过
if (dp[j - coins[i]] != INT_MAX) {
dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
}
}
}
if (dp[amount] == INT_MAX) { return -1; }
return dp[amount];
}
};
Problem: Given an integer n, return the least number of perfect square numbers that sum to n. A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.
Case 1: Input: n = 12, Output: 3
Case 2: Input: n = 13, Output: 2
class Solution {
public:
int numSquares(int n) {
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;
for (int i = 0; i <= n; i++) { // 遍历背包
for (int j = 1; j * j <= i; j++) { // 遍历物品
dp[i] = min(dp[i - j * j] + 1, dp[i]);
}
}
return dp[n];
}
};
17. 139. Word Break
Problem: Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words. Note that the same word in the dictionary may be reused multiple times in the segmentation.
Case 1: Input: s = “leetcode”, wordDict = [“leet”,”code”], Output: true
Case 2: Input: s = “applepenapple”, wordDict = [“apple”,”pen”], Output: true
Case 3: Input: s = “catsandog”, wordDict = [“cats”,”dog”,”sand”,”and”,”cat”], Output: false
class Solution {
public:
// 时间复杂度: O(n^3)
// 空间复杂度: O(n)
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
vector<bool> dp(s.size() + 1, false);
dp[0] = true;
for (int i = 1; i <= s.size(); i++) { // 遍历背包
for (int j = 0; j < i; j++) { // 遍历物品
string word = s.substr(j, i - j); //substr(起始位置, 截取的个数)
if (wordSet.find(word) != wordSet.end() && dp[j]) {
dp[i] = true;
}
}
}
return dp[s.size()];
}
};
Problem: You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Case 1: Input: nums = [1,2,3,1], Output: 4
Case 2: Input: nums = [2,7,9,3,1], Output: 12
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() == 0) { return 0; }
if (nums.size() == 1) { return nums[0]; }
vector<int> dp(nums.size());
dp[0] = nums[0];
dp[1] = max(nums[0], nums[1]);
for (int i = 2; i < nums.size(); i++) {
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[nums.size() - 1];
}
};
Problem: You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed. All houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, adjacent houses have a security system connected, and it will automatically contact the police if two adjacent houses were broken into on the same night. Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Case 1: Input: nums = [2,3,2], Output: 3
Case 2: Input: nums = [1,2,3,1], Output: 4
Case 3: Input: nums = [1,2,3], Output: 3
class Solution {
public:
// 198.打家劫舍的逻辑
int robRange(vector<int>& nums, int start, int end) {
if (end == start) { return nums[start]; }
vector<int> dp(nums.size());
dp[start] = nums[start];
dp[start + 1] = max(nums[start], nums[start + 1]);
for (int i = start + 2; i <= end; i++) {
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[end];
}
int rob(vector<int>& nums) {
if (nums.size() == 0) { return 0; }
if (nums.size() == 1) { return nums[0]; }
int result1 = robRange(nums, 0, nums.size() - 2); // 情况二
int result2 = robRange(nums, 1, nums.size() - 1); // 情况三
return max(result1, result2);
}
};
Problem: The thief has found himself a new place for his thievery again. There is only one entrance to this area, called root. Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that all houses in this place form a binary tree. It will automatically contact the police if two directly-linked houses were broken into on the same night. Given the root of the binary tree, return the maximum amount of money the thief can rob without alerting the police.
Case 1: Input: root = [3,2,3,null,3,null,1], Output: 7
Case 2: Input: root = [3,4,5,1,3,null,1], Output: 9
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 时间复杂度: O(n)
// 空间复杂度: O(log n)
// 长度为2的数组
// 0: 不偷, 1: 偷
vector<int> robTree(TreeNode* cur) {
if (cur == NULL) { return vector<int>{0, 0}; }
// 后序遍历
vector<int> left = robTree(cur->left);
vector<int> right = robTree(cur->right);
// 偷cur节点, 那么就不能偷左右节点
int val1 = cur->val + left[0] + right[0];
// 不偷cur节点, 那么可以偷也可以不偷左右节点, 则取较大的情况
int val2 = max(left[0], left[1]) + max(right[0], right[1]);
return {val2, val1};
}
int rob(TreeNode* root) {
vector<int> result = robTree(root);
// 偷根节点和不偷根节点取最大值
return max(result[0], result[1]);
}
};
21. 121. Best Time to Buy and Sell Stock
Problem: You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Case 1: Input: prices = [7,1,5,3,6,4], Output: 5
Case 2: Input: prices = [7,6,4,3,1], Output: 0
class Solution {
public:
// 时间复杂度: O(n)
// 空间复杂度: O(n)
int maxProfit(vector<int>& prices) {
int len = prices.size();
if (len == 0) { return 0; }
vector<vector<int>> dp(len, vector<int>(2));
dp[0][0] = -prices[0];
dp[0][1] = 0;
for (int i = 1; i < len; i++) {
dp[i][0] = max(dp[i - 1][0], -prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
}
return dp[len - 1][1];
}
};
22. 122. Best Time to Buy and Sell Stock II
Problem: You are given an integer array prices where prices[i] is the price of a given stock on the ith day. On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day. Find and return the maximum profit you can achieve.
Case 1: Input: prices = [7,1,5,3,6,4], Output: 7
Case 2: Input: prices = [1,2,3,4,5], Output: 4
Case 3: Input: prices = [7,6,4,3,1], Output: 0
class Solution {
public:
// 时间复杂度: O(n)
// 空间复杂度: O(n)
int maxProfit(vector<int>& prices) {
int len = prices.size();
if (len == 0) { return 0; }
vector<vector<int>> dp(len, vector<int>(2, 0));
dp[0][0] = -prices[0];
dp[0][1] = 0;
for (int i = 1; i < len; i++) {
// 注意这里是和121买卖股票的最佳时机唯一不同的地方
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[len - 1][1];
}
};
23. 123. Best Time to Buy and Sell Stock III
Problem: You are given an array prices where prices[i] is the price of a given stock on the ith day. Find the maximum profit you can achieve. You may complete at most two transactions. Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Case 1: Input: prices = [3,3,5,0,0,3,1,4], Output: 6
Case 2: Input: prices = [1,2,3,4,5], Output: 4
Case 3: Input: prices = [7,6,4,3,1], Output: 0
class Solution {
public:
// 时间复杂度: O(n)
// 空间复杂度: O(n × 5)
int maxProfit(vector<int>& prices) {
if (prices.size() == 0) { return 0; }
vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
dp[0][0] = 0;
dp[0][1] = -prices[0];
dp[0][2] = 0;
dp[0][3] = -prices[0];
dp[0][4] = 0;
for (int i = 1; i < prices.size(); i++) {
dp[i][0] = dp[i - 1][0];
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]); // 第一次持有
dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]); // 第一次不持有
dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]); // 第二次持有
dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]); // 第二次不持有
}
return dp[prices.size() - 1][4];
}
};
24. 188. Best Time to Buy and Sell Stock IV
Problem: You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k. Find the maximum profit you can achieve. You may complete at most k transactions. Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Case 1: Input: k = 2, prices = [2,4,1], Output: 2
Case 2: Input: k = 2, prices = [3,2,6,5,0,3], Output: 7
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
if (prices.size() == 0) { return 0; }
vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));
for (int j = 1; j < 2 * k; j += 2) {
dp[0][j] = -prices[0];
}
for (int i = 1;i < prices.size(); i++) {
for (int j = 0; j < 2 * k - 1; j += 2) {
dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);
dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);
}
}
return dp[prices.size() - 1][2 * k];
}
};
25. 309. Best Time to Buy and Sell Stock with Cooldown
Problem: You are given an array prices where prices[i] is the price of a given stock on the ith day. Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times) with the following restrictions: After you sell your stock, you cannot buy stock on the next day (i.e., cooldown one day). Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Case 1: Input: prices = [1,2,3,0,2], Output: 3
Case 2: Input: prices = [1], Output: 0
class Solution {
public:
// 时间复杂度: O(n)
// 空间复杂度: O(n)
int maxProfit(vector<int>& prices) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(4, 0));
// dp[i][0]: 持有股票
// dp[i][1]: 保持卖出股票
// dp[i][2]: 卖出股票
// dp[i][3]: 冷冻期
dp[0][0] = -prices[0]; // 持股票
for (int i = 1; i < n; i++) {
dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]));
dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);
dp[i][2] = dp[i - 1][0] + prices[i];
dp[i][3] = dp[i - 1][2];
}
return max(dp[n - 1][3], max(dp[n - 1][1], dp[n - 1][2]));
}
};
26. 714. Best Time to Buy and Sell Stock with Transaction Fee
Problem: You are given an array prices where prices[i] is the price of a given stock on the ith day, and an integer fee representing a transaction fee. Find the maximum profit you can achieve. You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Case 1: Input: prices = [1,3,2,8,4,9], fee = 2, Output: 8
Case 2: Input: prices = [1,3,7,5,10,3], fee = 3, Output: 6
class Solution {
public:
// 时间复杂度: O(n)
// 空间复杂度: O(n)
int maxProfit(vector<int>& prices, int fee) {
int n = prices.size();
vector<vector<int>> dp(n, vector<int>(2, 0));
dp[0][0] -= 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] - fee);
}
return max(dp[n - 1][0], dp[n - 1][1]);
}
};
27. 300. Longest Increasing Subsequence
Problem: Given an integer array nums, return the length of the longest strictly increasing subsequence.
Case 1: Input: nums = [10,9,2,5,3,7,101,18], Output: 4
Case 2: Input: nums = [0,1,0,3,2,3], Output: 4
Case 2: Input: nums = [7,7,7,7,7,7,7], Output: 1
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
if (nums.size() <= 1) { return nums.size(); }
vector<int> dp(nums.size(), 1);
int result = 0;
for (int i = 1; i < nums.size(); i++) {
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) { dp[i] = max(dp[i], dp[j] + 1); }
}
if (dp[i] > result) { result = dp[i]; } // 取长的子序列
}
return result;
}
};
28. 674. Longest Continuous Increasing Subsequence
Problem: Given an unsorted array of integers nums, return the length of the longest continuous increasing subsequence (i.e. subarray). The subsequence must be strictly increasing. A continuous increasing subsequence is defined by two indices l and r (l < r) such that it is [nums[l], nums[l + 1], …, nums[r – 1], nums[r]] and for each l <= i < r, nums[i] < nums[i + 1].
Case 1: Input: nums = [1,3,5,4,7], Output: 3
Case 2: Input: nums = [2,2,2,2,2], Output: 1
class Solution {
public:
// 时间复杂度: O(n)
// 空间复杂度: O(n)
int findLengthOfLCIS(vector<int>& nums) {
if (nums.size() == 0) { return 0; }
int result = 1;
vector<int> dp(nums.size() ,1);
for (int i = 1; i < nums.size(); i++) {
if (nums[i] > nums[i - 1]) { // 连续记录
dp[i] = dp[i - 1] + 1;
}
if (dp[i] > result) {result = dp[i];}
}
return result;
}
};
29. 718. Maximum Length of Repeated Subarray
Problem: Given two integer arrays nums1 and nums2, return the maximum length of a subarray that appears in both arrays.
Case 1: Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7], Output: 3
Case 2: Input: nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0], Output: 5
class Solution {
public:
// 时间复杂度: O(n × m), n 为A长度, m为B长度
// 空间复杂度: O(n × m)
int findLength(vector<int>& nums1, vector<int>& nums2) {
vector<vector<int>> dp (nums1.size() + 1, vector<int>(nums2.size() + 1, 0));
int result = 0;
for (int i = 1; i <= nums1.size(); i++) {
for (int j = 1; j <= nums2.size(); j++) {
if (nums1[i - 1] == nums2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}
if (dp[i][j] > result) { result = dp[i][j]; }
}
}
return result;
}
};
30. 1143. Longest Common Subsequence
Problem: Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0. A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters. For example, “ace” is a subsequence of “abcde”. A common subsequence of two strings is a subsequence that is common to both strings.
Case 1: Input: text1 = “abcde”, text2 = “ace”, Output: 3
Case 2: Input: text1 = “abc”, text2 = “abc”, Output: 3
Case 3: Input: text1 = “abc”, text2 = “def”, Output: 0
class Solution {
public:
int longestCommonSubsequence(string text1, string text2) {
vector<vector<int>> dp(text1.size() + 1, vector<int>(text2.size() + 1, 0));
for (int i = 1; i <= text1.size(); i++) {
for (int j = 1; j <= text2.size(); 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[text1.size()][text2.size()];
}
};
Problem: You are given two integer arrays nums1 and nums2. We write the integers of nums1 and nums2 (in the order they are given) on two separate horizontal lines. We may draw connecting lines: a straight line connecting two numbers nums1[i] and nums2[j] such that: (1) nums1[i] == nums2[j], and (2) the line we draw does not intersect any other connecting (non-horizontal) line. Note that a connecting line cannot intersect even at the endpoints (i.e., each number can only belong to one connecting line). Return the maximum number of connecting lines we can draw in this way.
Case 1: Input: nums1 = [1,4,2], nums2 = [1,2,4], Output: 2
Case 2: Input: nums1 = [2,5,1,2,5], nums2 = [10,5,2,1,5,2], Output: 3
Case 3: Input: nums1 = [1,3,7,1,7,5], nums2 = [1,9,2,5,1], Output: 2
class Solution {
public:
int maxUncrossedLines(vector<int>& A, vector<int>& B) {
vector<vector<int>> dp(A.size() + 1, vector<int>(B.size() + 1, 0));
for (int i = 1; i <= A.size(); i++) {
for (int j = 1; j <= B.size(); j++) {
if (A[i - 1] == B[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[A.size()][B.size()];
}
};
Problem: Given an integer array nums, find the subarray with the largest sum, and return its sum.
Case 1: Input: nums = [-2,1,-3,4,-1,2,1,-5,4], Output: 6
Case 2: Input: nums = [1], Output: 1
Case 3: Input: nums = [5,4,-1,7,8], Output: 23
// Dynamic Programming Method
class Solution {
public:
// 时间复杂度：O(n)
// 空间复杂度：O(n)
int maxSubArray(vector<int>& nums) {
if (nums.size() == 0) return 0;
vector<int> dp(nums.size());
dp[0] = nums[0];
int result = dp[0];
for (int i = 1; i < nums.size(); i++) {
dp[i] = max(dp[i - 1] + nums[i], nums[i]); // 状态转移公式
if (dp[i] > result) result = dp[i]; // result 保存dp[i]的最大值
}
return result;
}
};
Problem: Given two strings s and t, return true if s is a subsequence of t, or false otherwise. A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., “ace” is a subsequence of “abcde” while “aec” is not).
Case 1: Input: s = “abc”, t = “ahbgdc”, Output: true
Case 2: Input: s = “axc”, t = “ahbgdc”, Output: false
class Solution {
public:
// 时间复杂度: O(n × m)
// 空间复杂度: O(n × m)
bool isSubsequence(string s, string t) {
vector<vector<int>> dp(s.size() + 1, vector<int>(t.size() + 1, 0));
for (int i = 1; i <= s.size(); i++) {
for (int j = 1; j <= t.size(); j++) {
if (s[i - 1] == t[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
dp[i][j] = dp[i][j - 1];
}
}
}
if (dp[s.size()][t.size()] == s.size()) { return true; }
return false;
}
};
34. 115. Distinct Subsequences
Problem: Given two strings s and t, return the number of distinct subsequences of s which equals t. The test cases are generated so that the answer fits on a 32-bit signed integer.
Case 1: Input: s = “rabbbit”, t = “rabbit”, Output: 3
Case 2: Input: s = “babgbag”, t = “bag”, Output: 5
class Solution {
public:
int numDistinct(string s, string t) {
vector<vector<uint64_t>> dp(s.size() + 1, vector<uint64_t>(t.size() + 1));
for (int i = 0; i < s.size(); i++) { dp[i][0] = 1; }
for (int j = 1; j < t.size(); j++) { dp[0][j] = 0; }
for (int i = 1; i <= s.size(); i++) {
for (int j = 1; j <= t.size(); j++) {
if (s[i - 1] == t[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[s.size()][t.size()];
}
};
35. 583. Delete Operation for Two Strings
Problem: Given two strings word1 and word2, return the minimum number of steps required to make word1 and word2 the same. In one step, you can delete exactly one character in either string.
Case 1: Input: word1 = “sea”, word2 = “eat”, Output: 2
Case 2: Input: word1 = “leetcode”, word2 = “etco”, Output: 4
class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1));
for (int i = 0; i <= word1.size(); i++) { dp[i][0] = i; }
for (int j = 0; j <= word2.size(); j++) { dp[0][j] = j; }
for (int i = 1; i <= word1.size(); i++) {
for (int j = 1; j <= word2.size(); j++) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);
}
}
}
return dp[word1.size()][word2.size()];
}
};
Problem: Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. You have the following three operations permitted on a word:
Insert a character
Delete a character
Replace a character
Case 1: Input: word1 = “horse”, word2 = “ros”, Output: 3
Case 2: Input: word1 = “intention”, word2 = “execution”, Output: 5
class Solution {
public:
int minDistance(string word1, string word2) {
vector<vector<int>> dp(word1.size() + 1, vector<int>(word2.size() + 1, 0));
for (int i = 0; i <= word1.size(); i++) { dp[i][0] = i; }
for (int j = 0; j <= word2.size(); j++) { dp[0][j] = j; }
for (int i = 1; i <= word1.size(); i++) {
for (int j = 1; j <= word2.size(); j++) {
if (word1[i - 1] == word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
}
else {
dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]}) + 1;
}
}
}
return dp[word1.size()][word2.size()];
}
};
37. 647. Palindromic Substrings
Problem: Given a string s, return the number of palindromic substrings in it. A string is a palindrome when it reads the same backward as forward. A substring is a contiguous sequence of characters within the string.
Case 1: Input: s = “abc”, Output: 3
Case 2: Input: s = “aaa”, Output: 6
class Solution {
public:
// 时间复杂度: O(n^2)
// 空间复杂度: O(n^2)
int countSubstrings(string s) {
vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
int result = 0;
for (int i = s.size() - 1; i >= 0; i--) {
for (int j = i; j < s.size(); j++) {
if (s[i] == s[j] && (j - i <= 1 || dp[i + 1][j - 1])) {
result++;
dp[i][j] = true;
}
}
}
return result;
}
};
38. 516. Longest Palindromic Subsequence
Problem: Given a string s, find the longest palindromic subsequence‘s length in s. A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
Case 1: Input: s = “bbbab”, Output: 4
Case 2: Input: s = “cbbd”, Output: 2
class Solution {
public:
int longestPalindromeSubseq(string s) {
vector<vector<int>> dp(s.size(), vector<int>(s.size(), 0));
for (int i = 0; i < s.size(); i++) dp[i][i] = 1;
for (int i = s.size() - 1; i >= 0; i--) {
for (int j = i + 1; j < s.size(); j++) {
if (s[i] == s[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2;
} else {
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
}
}
}
return dp[0][s.size() - 1];
}
};