题目
解题
方法一：回溯（超时）
class Solution { public: int res=0; int tmp=0; void backtracing(int n){ if(tmp==n){ res++; }else if(tmp>n) return; for(int i=1;i<=2;i++){ tmp+=i; backtracing(n); tmp-=i; } } int climbStairs(int n) { backtracing(n); return res; } };
方法二：动态规划
class Solution { public: int climbStairs(int n) { if(n<=1) return n; vector<int> dp(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]; } };
方法三:动态规划（完全背包）
由于步数1和2可以无限使用的，因此可以看成完全背包
如果要达到3个台阶，可以先走1步再走2步，或者先2步后一步，是两种情况，因此又是排列问题，不是组合。
完全背包=》容量从头开始遍历
排列问题=》先遍历容量，再遍历 物体。
class Solution { public: int climbStairs(int n) { vector<int> dp(n+1); dp[0]=1; vector<int> nums={1,2}; for(int i=0;i<=n;i++){ for(int j=0;j<nums.size();j++){ if(i-nums[j]>=0&&dp[i]<INT_MAX-dp[i-nums[j]]){ dp[i]+=dp[i-nums[j]]; } } } return dp[n]; } };
