动态规划（基础版）
2024年1月23日大约 12 分钟
70. 爬楼梯
假设你正在爬楼梯。需要
n阶你才能到达楼顶。每次你可以爬
1或2个台阶。你有多少种不同的方法可以爬到楼顶呢?
class Solution {
public:
int climbStairs(int n) {
//dp(n) 表示爬到第 n 级台阶的方案数
int dp[n+1];
dp[0] = dp[1] = 1;//初始化
for(int i = 2;i <= n;i++) {
dp[i] = dp[i-1] + dp[i-2];//状态转移方程
}
return dp[n];
}
};509. 斐波那契数
斐波那契数 （通常用
F(n)表示）形成的序列称为 斐波那契数列 。该数列由0和1开始，后面的每一项数字都是前面两项数字的和。也就是：F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1给定
n，请计算F(n)。
class Solution {
public:
int fib(int n) {
if(n == 0||n == 1) return n;
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];
}
};1137. 第 N 个泰波那契数
泰波那契序列 Tn 定义如下：
T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
给你整数
n，请返回第 n 个泰波那契数 Tn 的值。
class Solution {
public:
int tribonacci(int n) {
//处理边界情况
if( n == 0 || n == 1) return n;
vector<int> dp(n + 1);
// 初始化
dp[0] = 0, dp[1] = 1, dp[2] = 1;
// 状态转移方程
for(int i = 3; i <= n; i++)
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
return dp[n];
}
};746. 使用最小花费爬楼梯
给你一个整数数组
cost，其中cost[i]是从楼梯第i个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。你可以选择从下标为
0或下标为1的台阶开始爬楼梯。请你计算并返回达到楼梯顶部的最低花费。
示例 ：
输入：cost = [10,15,20] 输出：15 解释：你将从下标为 1 的台阶开始。 - 支付 15 ，向上爬两个台阶，到达楼梯顶部。 总花费为 15 。
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int n = cost.size();
//minCost[i]表示达到下标 i 的最小花费。
vector<int> minCost(n+1,0);
for(int i = 2; i <= n; i++) {
// 状态转移方程
minCost[i] = min(minCost[i-1]+cost[i-1],minCost[i-2]+cost[i-2]);
}
return minCost[n];
}
};198. 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
示例 ：
输入：[1,2,3,1] 输出：4 解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
//用 dp[i]表示前 i 间房屋能偷窃到的最高总金额
vector<int> dp(n+1,0);
dp[0] = 0;
dp[1] = nums[0];
for(int i = 2; i <= n;i++){
// 状态转移方程
dp[i] = max(dp[i-2] + nums[i-1],dp[i-1]);
}
return dp[n];
}
};740. 删除并获得点数
给你一个整数数组
nums，你可以对它进行一些操作。每次操作中，选择任意一个
nums[i]，删除它并获得nums[i]的点数。之后，你必须删除 所有 等于nums[i] - 1和nums[i] + 1的元素。开始你拥有
0个点数。返回你能通过这些操作获得的最大点数。示例：
输入：nums = [3,4,2] 输出：6 解释： 删除 4 获得 4 个点数，因此 3 也被删除。 之后，删除 2 获得 2 个点数。总共获得 6 个点数。
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
vector<int> dp(n+1,0);
dp[0] = 0;
dp[1] = nums[0];
for(int i = 2; i <= n;i++){
// 状态转移方程
dp[i] = max(dp[i-2] + nums[i-1],dp[i-1]);
}
return dp[n];
}
int deleteAndEarn(vector<int>& nums) {
int maxVal = 0;
for (int val : nums) {
maxVal = max(maxVal, val);
}
vector<int> sum(maxVal + 1);
for (int val : nums) {
sum[val] += val;
}
return rob(sum);
}
};62. 不同路径
一个机器人位于一个
m x n网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 ：
img 输入：m = 3, n = 7 输出：28
class Solution {
public:
int uniquePaths(int m, int n) {
int dp[m][n];
for(int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for(int i = 0; i < n; i++) {
dp[0][i] = 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];
}
};
//此外，由于 f(i,j)仅与第 i 行和第 i−1 行的状态有关，因此我们可以使用滚动数组代替代码中的二维数组，使空间复杂度降低为 O(n)
class Solution {
public:
int uniquePaths(int m, int n) {
vector<int> f(n,1);
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
f[j]+=f[j-1];
}
}
return f[n - 1];
}
};64. 最小路径和
给定一个包含非负整数的
m x n网格grid，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。**说明：**每次只能向下或者向右移动一步。
示例 ：
img 输入：grid = [[1,3,1],[1,5,1],[4,2,1]] 输出：7 解释：因为路径 1→3→1→1→1 的总和最小。
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();int n = grid[0].size();
vector<vector<int>> dp(m,vector<int>(n,0));
dp[0][0] = grid[0][0];
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++) {
if(i==0 && j==0) continue;
else if(i==0&&j>0) dp[i][j] = dp[i][j-1] + grid[0][j];
else if(j==0&&i>0) dp[i][j] = dp[i-1][j] + grid[i][0];
// 状态转移方程
else dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j];
}
}
return dp[m-1][n-1];
}
};63. 不同路径 II
一个机器人位于一个
m x n网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用
1和0来表示。示例 ：
img 输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]] 输出：2 解释：3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径： 1. 向右 -> 向右 -> 向下 -> 向下 2. 向下 -> 向下 -> 向右 -> 向右
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<int> dp(n);
dp[0] = (obstacleGrid[0][0] == 0);
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(obstacleGrid[i][j] == 1)
{
dp[j] = 0;
continue;
}
if(j > 0) dp[j] += dp[j-1];
}
}
return dp[n-1];
}
};120. 三角形最小路径和
给定一个三角形
triangle，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标
i，那么下一步可以移动到下一行的下标i或i + 1。示例 ：
输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]] 输出：11 解释：如下面简图所示： 2 3 4 6 5 7 4 1 8 3 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。
class Solution {
public:
int minimumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
vector<vector<int>> dp(n,vector<int>(n));
dp[0][0] = triangle[0][0];
for(int i = 1; i < n; i++) {
dp[i][0] = dp[i-1][0] + triangle[i][0];
for(int j = 1; j < i; j++) {
dp[i][j] = min(dp[i-1][j-1],dp[i-1][j]) + triangle[i][j];
}
dp[i][i] = dp[i-1][i-1] + triangle[i][i];
}
//return *min_element(dp[n - 1].begin(), dp[n - 1].end());
//也可以自己写求最小值如下：
int res = dp[n-1][0];
for(int i = 0; i < n; i++) {
if(res > dp[n-1][i]) res = dp[n-1][i];
}
return res;
}
};931. 下降路径最小和
给你一个
n x n的 方形 整数数组matrix，请你找出并返回通过matrix的下降路径 的 最小和 。下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置
(row, col)的下一个元素应当是(row + 1, col - 1)、(row + 1, col)或者(row + 1, col + 1)。示例 ：
img 输入：matrix = [[2,1,3],[6,5,4],[7,8,9]] 输出：13 解释：如图所示，为和最小的两条下降路径
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& matrix) {
int n = matrix.size();
vector<vector<int>> dp(n,vector<int>(n));
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(i == 0) {
dp[i][j] = matrix[i][j];
continue;
}
if(j == 0) {
dp[i][j] = matrix[i][j] + min(dp[i-1][j+1],dp[i-1][j]);
continue;
}
if(j == n-1) {
dp[i][j] = matrix[i][j] + min(dp[i-1][j-1],dp[i-1][j]);
continue;
}
dp[i][j] = matrix[i][j] + min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j+1]));
}
}
return *min_element(dp[n - 1].begin(), dp[n - 1].end());
}
};221. 最大正方形
在一个由
'0'和'1'组成的二维矩阵内，找到只包含'1'的最大正方形，并返回其面积。示例 ：
img 输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]] 输出：4
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
int maxSide = 0;
//dp(i,j) 表示以 (i,j) 为右下角，且只包含 1 的正方形的边长最大值
vector<vector<int>> dp(m,vector<int>(n,0));
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(matrix[i][j] == '1') {
if(i == 0 || j == 0) {
dp[i][j] = 1;
}
else {
// 状态转移方程,如果该位置的值是 1
// 则 dp(i,j)的值由其上方、左方和左上方的三个相邻位置的 dp 值决定
dp[i][j] = min(min(dp[i-1][j],dp[i-1][j-1]),dp[i][j-1]) + 1;
}
maxSide = max(maxSide,dp[i][j]);
}
}
}
return maxSide*maxSide;
}
};5. 最长回文子串
给你一个字符串
s，找到s中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。示例 2：
输入：s = "cbbd" 输出："bb"
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
if (n < 2) {
return s;
}
int maxLen = 1;
int begin = 0;
// dp[i][j] 表示 s[i..j] 是否是回文串
vector<vector<int>> dp(n, vector<int>(n));
// 初始化：所有长度为 1 的子串都是回文串
for (int i = 0; i < n; i++) {
dp[i][i] = true;
}
// 递推开始
// 先枚举子串长度
for (int L = 2; L <= n; L++) {
// 枚举左边界，左边界的上限设置可以宽松一些
for (int i = 0; i < n; i++) {
// 由 L 和 i 可以确定右边界，即 j - i + 1 = L 得
int j = L + i - 1;
// 如果右边界越界，就可以退出当前循环
if (j >= n) {
break;
}
if (s[i] != s[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
// 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substr(begin, maxLen);
}
};139. 单词拆分
给你一个字符串
s和一个字符串列表wordDict作为字典。如果可以利用字典中出现的一个或多个单词拼接出s则返回true。**注意：**不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"] 输出: true 解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"] 输出: true 解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。 注意，你可以重复使用字典中的单词。示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"] 输出: false
class Solution {
public:
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);
//dp[i]=dp[j] && check(s[j..i−1])
if(wordSet.find(word)!=wordSet.end() && dp[j]){
dp[i] = true;
}
}
}
return dp[s.size()];
}
};343. 整数拆分
给定一个正整数
n，将其拆分为k个 正整数 的和（k >= 2），并使这些整数的乘积最大化。返回 你可以获得的最大乘积 。
示例 1:
输入: n = 2 输出: 1 解释: 2 = 1 + 1, 1 × 1 = 1。示例 2:
输入: n = 10 输出: 36 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。提示:
2 <= n <= 58
class Solution {
public:
int integerBreak(int n) {
// dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
// 将i拆成j(单个数) 和 i - j (可以为1个或单个数，因为i-j 始终 >=j，所以i
// - j可能再拆为多个数)， j <= i/2
vector<int> dp(n + 1);// dp[i] 表示拆分数值i可得的最大乘积
dp[0] = 0;
dp[1] = 0;
dp[2] = 1;
for (int i = 3; i <= n; i++) {
for (int j = 1; j <= i / 2; j++) {
dp[i] = max(max(j * (i - j), j * dp[i - j]), dp[i]);
}
}
return dp[n];
}
};