爬樓梯問題
1. 題目
爬樓梯每次可以爬1階或兩階践宴，問到n階有多少種方法
2. 思路
狀態(tài)：dp[i]表示到第i階的走法
狀態(tài)轉(zhuǎn)移方程：dp[i] = dp[i-1] + dp[i-2]
邊界狀態(tài)值：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個(gè)房屋，每個(gè)房屋有不等數(shù)量的財(cái)寶错负，盜賊想要盜取財(cái)物婿着，但是從相鄰的房屋盜取會(huì)出發(fā)警報(bào)沿侈，問在不觸發(fā)警報(bào)的情況下衣形，最多可以盜取多少財(cái)寶翎苫？
2. 思路
- 狀態(tài)：dp[i]表示前i個(gè)房間能獲得的最大財(cái)寶
- 狀態(tài)轉(zhuǎn)移方程：
如果選擇第i個(gè)房間，dp[i] = dp[i-2] + dp[i]铁蹈；不選擇第i個(gè)房間宽闲，dp[i] = dp[i-1]；
所以dp[i]的最優(yōu)解為dp[i] = max(dp[i-2] + dp[i], dp[i-1]) - 邊界狀態(tài)值：
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. 題目
給定一個(gè)數(shù)組握牧，求這個(gè)數(shù)組的連續(xù)子數(shù)組中，最大的那一段的和
2. 思路
- 狀態(tài)：dp[i] 表示以第i個(gè)數(shù)字結(jié)尾的最大子段和
- 狀態(tài)轉(zhuǎn)移方程
若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]) - 邊界狀態(tà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]); // 狀態(tài)轉(zhuǎn)移方程
if (max_res < dp[i]) {
max_res = dp[i];
}
}
return max_res;
}
