目录
动态规划
使用最小花费爬楼梯
题目
数组的每个索引作为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 costi。
每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。
代码
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
// 一旦支付了相应的体力值，就可以选择向上爬一个阶梯或者爬两个阶梯。
// 找出达到楼层顶部的最低花费
// 在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯
vector<int> dp(cost.size() + 1, 0);
//3.dp初始化
dp[0]=0;
dp[1]=0;
// 1.dp[i] 表示到达第i个位置的最低花费
//2.递推公式 4.确定遍历顺序 5.打印dp数组
for(int i=2;i<=cost.size();i++){
dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
}
return dp[cost.size()];
}
};
int main(){
int n;
cin>>n;
int e;
vector<int> cost;
for(int i=0;i<n;i++){
cin>>e;
cost.push_back(e);
}
int res=Solution().minCostClimbingStairs(cost);
cout<<res<<endl;
return 0;
}
不同路径
题目
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
问总共有多少条不同的路径？
代码
#include <iostream>
#include <vector>
class Solution {
public:
static int uniquePaths(int m, int n) {
// 使用vector定义dp数组
std::vector<std::vector<int>> dp(m, std::vector<int>(n, 0));
// 初始化
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];
}
};
int main() {
int m, n;
std::cin >> m >> n;
std::cout << Solution::uniquePaths(m, n) << std::endl;
return 0;
}
不同路径 II
题目
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
代码
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& nums) {
int n = nums.size(), m = nums[0].size();
vector<vector<long long>> f(n, vector<long long>(m, 0));
// 初始化起点，如果起点有障碍物，则直接返回0
if (nums[0][0] == 0) f[0][0] = 1;
// 计算第一行的路径数，跳过障碍物
for (int j = 0; j < m; j++) {
if (nums[0][j] == 0 && (j == 0 || nums[0][j - 1] == 0)) {
f[0][j] = 1;
} else {
break;
}
}
// 计算第一列的路径数，跳过障碍物
for (int i = 0; i < n; i++) {
if (nums[i][0] == 0 && (i == 0 || nums[i - 1][0] == 0)) {
f[i][0] = 1;
} else {
break;
}
}
// 计算其他位置的路径数
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
if (nums[i][j] == 0) {
f[i][j] = f[i - 1][j] + f[i][j - 1];
}
}
}
return f[n - 1][m - 1];
}
};
int main() {
int m, n;
cin >> m >> n;
vector<vector<int>> obstacleGrid(m, vector<int>(n));
for (int i = 0; i < m; ++i) {
string line;
cin >> line;
for (int j = 0; j < n; ++j) {
obstacleGrid[i][j] = line[j] - '0'; // 将字符0或1转换为整数0或1
}
}
Solution sol;
cout << sol.uniquePathsWithObstacles(obstacleGrid) << endl;
return 0;
}
最佳买卖股票时机含冷冻期
题目
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
代码
#include <iostream>
#include <vector>
#include <algorithm> // 用于std::max函数
using namespace std;
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
if (n < 2) return 0; // 如果天数少于2天，则无法进行交易
vector<vector<int>> dp(n, vector<int>(3, 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][2]); // 今天不持有股票且不进行操作
dp[i][2] = dp[i - 1][0] + prices[i]; // 今天卖出股票
}
return max(dp[n - 1][1], dp[n - 1][2]); // 最后一天不持有股票或者卖出股票
}
};
int main() {
int n;
cin >> n;
vector<int> prices(n);
for (int i = 0; i < n; ++i) {
cin >> prices[i];
}
Solution sol;
int res = sol.maxProfit(prices);
cout << res << endl;
return 0;
}
单词拆分
题目
给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。
说明：
拆分时可以重复使用字典中的单词。
你可以假设字典中没有重复的单词。
代码
#include <bits/stdc++.h>
using namespace std;
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++) {
if (dp[j] && wordSet.count(s.substr(j, i - j))) {
dp[i] = true;
break;
}
}
}
return dp[s.size()];
}
};
int main() {
string s;
int n;
cin >> s;
cin >> n;
vector<string> wordDict;
for (int i = 0; i < n; i++) {
string word;
cin >> word;
wordDict.push_back(word);
}
bool res = Solution().wordBreak(s, wordDict);
cout << (res ? "true" : "false") << endl;
return 0;
}
整数拆分
题目
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
代码
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int integerBreak(int n) {
vector<int> dp(n + 1);
dp[2] = 1;
for (int i = 3; i <= n ; i++) {
for (int j = 1; j < i - 1; j++) {
dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
}
}
return dp[n];
}
};
int main(){
int n;
cin>>n;
int res=Solution().integerBreak(n);
cout<<res<<endl;
return 0;
}
等差数列划分
题目
如果一个数列至少有三个元素，并且任意两个相邻元素之差相同，则称该数列为等差数列。
例如，以下数列为等差数列:
1, 3, 5, 7, 9
7, 7, 7, 7
3, -1, -5, -9
以下数列不是等差数列。
1, 1, 2, 5, 7
数组 A 包含 N 个数，且索引从0开始。数组 A 的一个子数组划分为数组 (P, Q)，P 与 Q 是整数且满足 0<=P<Q<N 。
如果满足以下条件，则称子数组(P, Q)为等差数组：
元素 A[P], A[p + 1], …, A[Q - 1], A[Q] 是等差的。并且 P + 1 < Q
函数要返回数组 A 中所有为等差数组的子数组个数。
示例:
A = [1, 2, 3, 4]
返回: 3, A 中有三个子等差数组: [1, 2, 3], [2, 3, 4] 以及自身 [1, 2, 3, 4]。
代码
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& nums) {
int n = nums.size();
if (n < 3) return 0; // 如果数组长度小于3，不可能形成等差数列
vector<int> dp(n, 0); // 初始化dp数组
int sum = 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; // 当前位置的等差数列数量是前一个位置的等差数列数量加1
sum += dp[i]; // 累加到总数量中
}
}
return sum;
}
};
int main() {
int n;
cin >> n; // 读取数组的长度
vector<int> nums(n);
for (int i = 0; i < n; i++) {
cin >> nums[i]; // 读取数组元素
}
Solution sol;
int res = sol.numberOfArithmeticSlices(nums); // 计算等差数列的数量
cout << res << endl; // 输出结果
return 0;
}
最大正方形
题目
在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
代码
#include <iostream>
#include <vector>
#include <algorithm> // 用于max函数
using namespace std;
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int m = matrix.size();
if (m == 0) return 0;
int n = matrix[0].size();
if (n == 0) return 0;
vector<vector<int>> dp(m, vector<int>(n, 0));
int ans = 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 {
dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
}
ans = max(ans, dp[i][j]);
}
}
}
return ans * ans;
}
};
int main() {
int m, n;
cin >> m >> n;
vector<vector<char>> matrix(m, vector<char>(n));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
cin >> matrix[i][j];
}
}
Solution sol;
int res = sol.maximalSquare(matrix);
cout << res << endl;
return 0;
}
戳气球
题目
有 n 个气球，编号为0 到 n-1，每个气球上都标有一个数字，这些数字存在数组 nums 中。
现在要求你戳破所有的气球。如果你戳破气球 i ，就可以获得 nums[left] * nums[i] * nums[right] 个硬币。 这里的 left 和 right 代表和 i 相邻的两个气球的序号。注意当你戳破了气球 i 后，气球 left 和气球 right 就变成了相邻的气球。
求所能获得硬币的最大数量。
代码
#include <iostream>
#include <vector>
#include <algorithm> // 用于max函数
using namespace std;
class Solution {
public:
int maxCoins(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> dp(n + 2, vector<int>(n + 2, 0));
vector<int> temp(n + 2);
// 辅助数组
temp[0] = temp[n + 1] = 1;
for (int i = 0; i < n; ++i) {
temp[i + 1] = nums[i];
}
// len表示开区间长度
for (int len = 3; len <= n + 2; len++) {
// i表示开区间的左端点(取不到 所以从0开始)
for (int l = 0; l <= n - len + 2; l++) {
// 右端点为：r = l + len - 1
int r = l + len - 1;
for (int k = l + 1; k < r; ++k) {
dp[l][r] = max(dp[l][r], dp[l][k] + temp[l] * temp[k] * temp[r] + dp[k][r]);
}
}
}
return dp[0][n + 1];
}
};
int main() {
int n;
cin >> n;
vector<int> nums(n);
for (int i = 0; i < n; ++i) {
cin >> nums[i];
}
Solution sol;
int res = sol.maxCoins(nums);
cout << res << endl;
return 0;
}
编辑距离
题目
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数 。
你可以对一个单词进行如下三种操作：
插入一个字符
删除一个字符
替换一个字符
代码
#include <iostream>
#include <vector>
#include <algorithm> // 用于std::min函数
using namespace std;
class 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 = 0; i <= m; ++i) {
dp[i][0] = i;
}
for (int j = 0; j <= n; ++j) {
dp[0][j] = j;
}
// 填充dp表
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] = 1 + min({dp[i - 1][j], // 删除操作
dp[i][j - 1], // 插入操作
dp[i - 1][j - 1] // 替换操作
});
}
}
}
return dp[m][n]; // 返回最短编辑距离
}
};
int main() {
string word1, word2;
cin >> word1;
cin >> word2;
Solution sol;
int result = sol.minDistance(word1, word2);
cout << result << endl;
return 0;
}