变态跳台阶

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

1.动态规划

台阶   跳法

 0           1

 1           1

 2           2

 3           4

 4           8

 看到这大概就差不多发现规律了，从第三项开始等于前面所有项的和，所以可以写出如下代码：

public class Solution {
    public int JumpFloorII(int n) {
        int []a=new int [n+1];
        a[1]=1;
        a[0]=1;
        if(n==1) return a[1]; 
        int s=1;
        for(int i=2;i<=n;i++){
         for(int j=0;j<i;j++){
          a[i]+=a[j];   
         }   
         
        }
        return a[n];
    }
}

如果去掉台阶数为0的情况可以得到a[i]=2*a[i-1]的规律，所以直接单重循环就足够了

台阶   跳法

 1           1

 2           2

 3           4

 4           8

代码如下：

public class Solution {
    public int JumpFloorII(int n) {
        int []a=new int [n+1];
        a[1]=1;
        if(n==1) return a[1]; 
        int s=1;
        for(int i=2;i<=n;i++){
        a[i]=a[i-1]*2;
        }

        return a[n];
    }
}

2.迭代

在发现a[i]=2*a[i-1]的情况下可以直接选择迭代;

代码如下：

public class Solution {
    public int JumpFloorII(int n) {

        int s=1;
        
        for(int i=2;i<=n;i++){
        s*=2;
        }

        return s;
    }
}