题目链接

爬楼梯

题目描述

image.png

实现代码

思路：首先可以知道，每一步都是有两个选择：走一步或者走两步，因此，可以采取dfs的方式进行递归；
实现代码：

  1. class Solution {
  3.     int result = 0;
  4.     public int climbStairs(int n) {
  6.         if(n <= 2) {
  7.             return n;
  8.         }
  9.         dfs(n);
  10.         return result;
  11.     }
  13.     public void dfs(int n) {
  15.         if(n < 0) {
  16.             return;
  17.         }
  19.         if(n <= 1) {
  20.             result++;
  21.             return;
  22.         }
  24.         dfs(n-1);
  25.         dfs(n-2);
  26.     }
  27. }

结果是正常的，但是运行超时了；

DP思路：记dp[i]表示当楼梯长度为i时的方法数量；可以知道dp[i]与dp[i-1]和dp[i-2]有关，因为只有这两个位置能够到达这里，因此状态转移方程为：

dp[i] = dp[i-1] + dp[i-2];

实现代码为：

  1. class Solution {
  3.     int result = 0;
  4.     public int climbStairs(int n) {
  6.         if(n <= 2) {
  7.             return n;
  8.         }
  10.         int[] dp = new int[n+1];
  11.         dp[0] = 0;
  12.         dp[1] = 1;
  13.         dp[2] = 2;
  15.         for(int i=3; i <= n; i++) {
  16.             dp[i] = dp[i-1] + dp[i-2];
  17.         }
  19.         return dp[n];
  20.     }
  21. }