【アルゴリズム】変態ステップ問題

タイトルの説明

1匹のカエルは一度に1段の階段を飛び上がることもできるし、2段も飛び上がることもできるし...n段も飛び上がることもできる.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.
分析:
カエルが1または2段しか踊らない場合、a[n]=a[n-1]+a[n-2]となると、1,2,3,・・、nステップ時a[n]=a[n-1]+a[n-2]+a[n-3]+......+a[0].
この繰返し式に基づいて、次のアルゴリズムが得られます.
         

 public int JumpFloorII(int target) {
        return jump(target);
        
    }
    
    int jump(int target){
        

		int a[]=new int[target+1];
        
		a[0]=1;
        a[1]=1;
        for(int i=2;i<=target;i++){
            a[i]=0;//a[i]=a[i-1]+a[i-2]+a[i-3]+.....a[0];
            for(int j=i-1;j>=0;j--){
                a[i]+=a[j];
            }
        }
        return a[target];
    }