例题
重述问题
找到最后一步
去掉最后一步，是否能划分出子问题
考虑边界
746. 使用最小花费爬楼梯
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int a=0,b=0;
for(int i=2;i<=(int)cost.size();++i) { int c=min(b+cost[i-1],a+cost[i-2]); a=b; b=c; }
return b;
}
};
剑指 Offer 42. 连续子数组的最大和
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int cur=nums[0],ans=cur;
for(int i=1;i<(int)nums.size();++i) { cur=max(nums[i],cur+nums[i]); ans=max(ans,cur); }
return ans;
}
};
343. 整数拆分
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int integerBreak(int n) {
vector<int> dp(n+1);
for(int i=2;i<=n;++i) for(int j=1;j<i;++j) dp[i]=max(dp[i],max(j*(i-j),j*dp[i-j]));
return dp[n];
}
};
322. 零钱兑换
每种硬币可使用任意次，面值须为正数。
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int coinChange(vector<int>& coins,int amount) {
vector<int> f(amount+1,amount+1); f[0]=0;
for(int i=1;i<=amount;++i) for(int c:coins) if(c<=i) f[i]=min(f[i],f[i-c]+1);
return f[amount]>amount?-1:f[amount];
}
};