climbing-stairs

题目描述

你在爬楼梯，需要n步才能爬到楼梯顶部

每次你只能向上爬1步或者2步。有多少种方法可以爬到楼梯顶部？

递归法：

 1 import java.util.*;
 2 
 3 
 4 public class Solution {
 5     /**
 6      * 
 7      * @param n int整型 
 8      * @return int整型
 9      */
10     public int climbStairs (int n) {
11         if(n==1) return 1;
12         if(n==2) return 2;
13         return climbStairs(n-1)+climbStairs(n-2);
14     }
15 }

备忘录法：

 1 import java.util.*;
 2 
 3 
 4 public class Solution {
 5     /**
 6      * 
 7      * @param n int整型 
 8      * @return int整型
 9      */
10     int[] dp=new int[1000];
11     public int climbStairs (int n) {
12         dp[1]=1;
13         dp[2]=2;
14         if(n==1) {
15             return 1;
16         }
17         if(n==2){
18             return 2;
19         } 
20         if(dp[n]!=0) return dp[n];
21         else{
22             dp[n]=climbStairs(n-1)+climbStairs(n-2);
23         }
24         return dp[n];
25     }
26 }

动态规划解法：

 1 import java.util.*;
 2 
 3 
 4 public class Solution {
 5     /**
 6      * 
 7      * @param n int整型 
 8      * @return int整型
 9      */
10     public int climbStairs (int n) {
11         if(n==1) return 1;
12         int[] dp=new int[n+1];
13         dp[1]=1;
14         dp[2]=2;
15         for(int i=3;i<=n;i++){
16             dp[i]=dp[i-1]+dp[i-2];
17         }
18         return dp[n];
19     }
20 }