每日一题：动态规划

如题（基础题）：

经典的爬楼梯问题，先从递归想起；

class Solution {
public:
    int climbStairs(int n) {
        if(n==1)
            return 1;
        if(n==2)
            return 2;

        return climbStairs(n-1)+climbStairs(n-2);
    }
};

之后可以想办法（如哈希表）去降低时间复杂度，即记忆化搜索或递归树的剪枝，避免对已经计算过的结点再次计算；

class Solution {
public:
    int climbStairs(int n) {
        int* memo=new int[n+1];
        return climbStairsMemo(n,memo);
    }

    int climbStairsMemo(int n,int memo[]){
        if(memo[n]>0){
            return memo[n];
        }
        if(n==1)
            memo[n]=1;
        else if(n==2)
            memo[n]=2;
        else{
            memo[n]=climbStairsMemo(n-1,memo)+climbStairsMemo(n-2,memo);
        }
        return memo[n];
    }
    
};

既然都有递归了，那肯定有非递归的解法（比如从n=1或n=2进行逆运算）；

class Solution {
public:
    int climbStairs(int n) {
        if(n==1){
            return 1;
        }
        int* dp=new int[n+1];
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};

扩展：斐波那契数列；

同上：

斐波那契数列的每一项是前两项之和，通常从 0 和 1 开始。用数学公式表示为：

F(n)=F(n−1)+F(n−2)

扩展：

递归：

class Solution {
public:
    int dfs(int n,vector<int>& cost){
        if(n<=1){
            return 0;
        }
        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();
        
        return dfs(n,cost);
    }
};//一般都超时

剪枝：

class Solution {
public:


    int minCostClimbingStairs(vector<int>& cost) {
        int n=cost.size();
        vector<int> memo(n+1,-1);
        function<int(int)> dfs=[&](int i)->int{
            if(memo[n]!=-1){
                return memo[n];
            }
            if(n<=1){
                return 0;
            }
            return memo[n]=min(dfs(n-1)+cost[n-1],dfs(n-2)+cost[n-2]);
        };

        return dfs(n);
    }
};

递推：

class Solution {
public:
    int minCostClimbingStairs(vector<int>& cost) {
        int n=cost.size();
        vector<int> dp(n+1);
        if(n<=1){
            dp[n]=0;
        }
        for(int i=2;i<=n;i++){
            dp[i]=min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[n];
    }
};