爬楼梯问题
1. 题目
爬楼梯每次可以爬1阶或两阶，问到n阶有多少种方法
2. 思路
状态：dp[i]表示到第i阶的走法
状态转移方程：dp[i] = dp[i-1] + dp[i-2]
边界状态值：dp[1] = 1, dp[2] = 2
3. 代码
int climbStairs(int n)
{
std::vector<int> dp(n+3, 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. 题目
一组相邻的n个房屋，每个房屋有不等数量的财宝，盗贼想要盗取财物，但是从相邻的房屋盗取会出发警报，问在不触发警报的情况下，最多可以盗取多少财宝？
2. 思路
- 状态：dp[i]表示前i个房间能获得的最大财宝
- 状态转移方程：
如果选择第i个房间，dp[i] = dp[i-2] + dp[i]；不选择第i个房间，dp[i] = dp[i-1]；
所以dp[i]的最优解为dp[i] = max(dp[i-2] + dp[i], dp[i-1]) - 边界状态值：
dp[0] = num[0],
dp[1] = max(num[0], num[1])
3. 代码
int rot(std::vector<int> &nums)
{
if (nums.size() == 0) {
return 0;
}
if (nums.size() == 1) {
return nums[0];
}
std::vector<int> dp(nums.size(), 0);
dp[0] = nums[0];
dp[1] = std::max(nums[0], nums[1]);
for (int i = 2; i < nums.size(); i++) {
dp[i] = std::max(dp[i-1], dp[i-2]+nums[i]);
}
return dp[nums.size() - 1 ];
}
最大子段和
1. 题目
给定一个数组，求这个数组的连续子数组中，最大的那一段的和
2. 思路
- 状态：dp[i] 表示以第i个数字结尾的最大子段和
- 状态转移方程
若dp[i-1] > 0, dp[i] = dp[i-1] + num[i]
若dp[i-1] < 0, dp[i] = num[i]
所以：dp[i] = max(dp[i-1] + num[i], num[i]) - 边界状态值：dp[0] = num[0]
3. 代码
int maxSubArray(std::vector<int> &num)
{
std::vector<int> dp(num.size(), 0);
dp[0] = num[0];
int max_res = dp[0];
for (int i = 1; i < num.size(); i++) {
dp[i] = std::max(dp[i - 1] + num[i], num[i]); // 状态转移方程
if (max_res < dp[i]) {
max_res = dp[i];
}
}
return max_res;
}
