本文最后更新于 77 天前，其中的信息可能已经有所发展或是发生改变。
例题
- 重述问题
- 找到最后一步
- 去掉最后一步，是否能划分出子问题
- 考虑边界
746. 使用最小花费爬楼梯
const int N=1010;
class Solution {
public:
int mem[N];
int dfs(vector<int>& cost, int x)
{
if(mem[x])return mem[x];
int sum=0;
if(x==1||x==0)sum=0;
else sum=min(dfs(cost,x-1)+cost[x-1],dfs(cost,x-2)+cost[x-2]);
mem[x]=sum;
return sum;
}
int minCostClimbingStairs(vector<int>& cost) {
int n=cost.size();
// int ans=dfs(cost,n);
int f[N];
f[0]=f[1]=0;
for(int i=2;i<=n;i++)
{
f[i]=min(f[i-1]+cost[i-1],f[i-2]+cost[i-2]);
}
return f[n];
}
};300. 最长递增子序列
const int N = 3010;
class Solution {
public:
int mem[N];
int dfs(vector<int>& nums, int x) {
if (mem[x])
return mem[x];
int res = 0;
for (int i = 0; i < x; i++) {
if (nums[i] < nums[x]) {
res = max(res, dfs(nums, i) + 1);
}
}
mem[x] = res;
return res;
}
int lengthOfLIS(vector<int>& nums) {
int n = nums.size();
int res=-1e9;
// for(int i=0;i<n;i++)
// {
// res=max(res,dfs(nums,i)+1);
// }
int f[N];
for (int i = 0; i < n; i++) {
f[i] = 1;
for (int j = 0; j < n; j++) {
if (nums[j] < nums[i]) {
f[i] = max(f[i], f[j] + 1);
}
}
}
for(int i=0;i<n;i++)
{
res=max(res,f[i]);
}
return res;
}
};322. 零钱兑换
const int N = 10010;
class Solution {
public:
int mem[N];
int dfs(vector<int>& coins, int amount) {
if (mem[amount])
return mem[amount];
int n = coins.size();
if (amount == 0)
return 0;
int res = 1e9;
for (int i = 0; i < n; i++) {
if (amount >= coins[i])
res = min(res, dfs(coins, amount - coins[i]) + 1);
}
mem[amount] = res;
return res;
}
int coinChange(vector<int>& coins, int amount) {
int n = coins.size();
// int ans = dfs(coins, amount);
// ans=ans==1e9?-1:ans;
int f[N];
memset(f, 0x3f, sizeof f);
f[0] = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < n; j++) {
if(i>=coins[j])
f[i]=min(f[i], f[i-coins[j]] + 1);
}
}
return f[amount]>1e9?-1:f[amount];
}
};剑指 Offer 42. 连续子数组的最大和
const int N=100010;
class Solution {
public:
int mem[N];
int dfs(vector<int>& sales,int x)
{
if(x<0)return 0;
if(mem[x])return mem[x];
int res=-1e9;
res=max(sales[x],dfs(sales,x-1)+sales[x]);
mem[x]=res;
return res;
}
int maxSales(vector<int>& sales) {
int n=sales.size();
int f[N];
int ans=-101;
// for(int i=0;i<n;i++)
// {
// ans=max(ans,dfs(sales,i));
// }
f[0]=sales[0];
for(int i=1;i<n;i++)
{
f[i]=max(sales[i],f[i-1]+sales[i]);
}
for(int i=0;i<n;i++)
{
ans=max(ans,f[i]);
}
return ans;
}
};343. 整数拆分
const int N=110;
class Solution {
public:
int mem[N]={0};
int dfs(int x)
{
if(mem[x])return mem[x];
if(x==0)return 1;
int res=0;
for(int i=1;i<x;i++)
{
res=max(res,max(i*(x-i),dfs(x-i)*i));
}
return mem[x]=res;
}
int integerBreak(int n) {
int ans;
// ans=dfs(n);
int dp[N];
dp[0] = dp[1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 1; j < i; ++j) {
dp[i] = max(dp[i], max(j * (i - j), dp[i - j] * j));
}
}
ans=dp[n];
return ans;
}
};
