动态规划基础篇（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<n;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];}
};