一、动态规划解题步骤：
1.1、题解
二、DFS暴搜
- 因为我们不确定开始是从第一/第二层开始搜所以可以逆向从最高层（n）开始搜索
class Solution
{
public:int dfs(int n,vector<int>& cost){if(n==0 || n==1) return 0; //从0/1开始爬，所以此时费用为0else return min(dfs(n-1,cost)+cost[n-1],dfs(n-2,cost)+cost[n-2]);}int minCostClimbingStairs(vector<int>& cost) {int n=cost.size();int res=dfs(n,cost);return res;}
};
三、记忆化搜索
- 注意此时虽然DFS的参数有两个，但是mem的参数可以只开一维，因为只有一个楼层数n影响到边界
const int N=1007;class Solution
{
public:int mem[N];int dfs(int n,vector<int>& cost){if(mem[n]) return mem[n];int sum=0;if(n==0 || n==1) sum = 0; //从0/1开始爬，所以此时费用为0else sum= min(dfs(n-1,cost)+cost[n-1],dfs(n-2,cost)+cost[n-2]);mem[n]=sum;return mem[n];}int minCostClimbingStairs(vector<int>& cost) {int n=cost.size();//memset(mem,0,sizeof(mem)); //初始化memint res=dfs(n,cost);return res;}
};
四、线性DP
- 此时的动态转移方程与DFS的递归方程基本一致
const int N=1007;class Solution
{
public:int mem[N];// int dfs(int n,vector<int>& cost)// {// if(mem[n]) return mem[n];// int sum=0;// if(n==0 || n==1) sum = 0; //从0/1开始爬，所以此时费用为0// else sum= min(dfs(n-1,cost)+cost[n-1],dfs(n-2,cost)+cost[n-2]);// mem[n]=sum;// return mem[n];// }int minCostClimbingStairs(vector<int>& cost) {int n=cost.size();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];}
};
