动态规划基础篇（LeetCode每日一题计划）

爬楼梯

求所有爬楼梯的方案

方法一：f(x)=f(x-1)+f(x-2)

class Solution {
    public int climbStairs(int n) {
        int p=0,q=0,r=1;
        for(int i=0;i
            p=q;
            q=r;
            r=p+q;
        }
        return r;
    }
}

方法二：动态规划

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

使用最小花费爬楼梯 

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int dp[]=new int[cost.length+1];
        dp[0]=dp[1]=0;
        for(int i=2;i<=cost.length;i++){
            dp[i]= Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[cost.length];
    }
}