算法－爬楼梯问题

一个Ｎ阶的楼梯，每次能１或着２阶，问走n阶的楼梯有多少种走法?

分析可知在走第ｎ阶的时候，是与第n-1阶和n-2阶有关系的。用户走到第ｎ阶的方法应该是用户走到第n-1 n-2阶的和。使用数学表达式应该 如下：

当n=1 或者n=2 时，f(n) = 1,所以我们可以考虑使用递归来实现

  　func ClimbStarisRecursion(n int) int{
          if n == 1 || n == 0{
              return 1
          }
          
          return ClimbStarisRecursion(n-2) + ClimbStarisRecursion(n-1)
     }

     func main(){
          step := 20
         fmt.Println(ClimbStarisRecursion(20))
     }

一般递归问题可以转换为动态规划问题来处理，相比于递归算法伴随这会伴随着较多的出栈入栈操作消耗，我们使用动态规划算法性能会优于递归算法，下面我们给出动态规划的版本

    func ClimbStarisDP(n int) int{
         pre := 1
         now := 1
         var tmp int
         for i := 2;i <= n;i++{
             tmp = now
             now = pre + now
             pre = tmp
        }   
        return now
    }

算法问题的计算过程中，最重要的抽象出问题中的数学模型，然后根据数学模型找到合适的计算方法(递归，动态规划，贪婪算法)进行代入求解是否能够得到需要的问题。