动态规划（线性DP）:DFS-＞记忆化-＞DP(Leetcode 746)

一、动态规划解题步骤：

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];}
};