ステップ問題(矩形オーバーライド問題)

ステップ問題
1匹のカエルは一度に1段の階段を飛び上がることも、2段を飛び上がることもできます.このカエルが1つのn級の階段を飛び上がるのが全部で何種類の跳び方があることを求めます(前後の順序が異なって異なる結果を計算します).
再帰的な問題です

n段のステップについて、f(n)種のジャンプ法があると仮定する.

初めて1段ジャンプをした場合、残りのn-1段にはf(n-1)種のジャンプ法

がある.

初めて2段ジャンプをした場合、残りのn-2段にはf(n-2)種のジャンプ法

がある.
前後順が異なるため,f(n)=f(n−1)+f(n−2)種のジャンプ法という2つの方式しかない.
再帰出口:n=1の場合、ジャンプ法は1つしかありません.n=2の場合、2つのジャンプ法(1,1および2)がある.
Demo:

int jumpFloor(int number) 
{
    if (number <= 0) return -1;
    else if (number == 1) return 1;
    else if (number == 2) return 2;
    else return jumpFloor(number-1) + jumpFloor(number-2);
}

 
へんたいステップ問題
1匹のカエルは一度に1段の階段を飛び上がることもできるし、2段も飛び上がることもできるし...n段も飛び上がることもできる.このカエルが1つのn級の階段を跳ぶことを求めて全部で何種類の跳び方があります.
前の問題に基づいて,1−n級ジャンプが可能になった.

n段のステップについて、f(n)種のジャンプ法があると仮定する.

初めて1段ジャンプをした場合、残りのn-1段にはf(n-1)種のジャンプ法

がある.

初めて2段ジャンプをした場合、残りのn-2段にはf(n-2)種のジャンプ法

がある.

初めて3段ジャンプをした場合、残りのn-3段にはf(n-3)種のジャンプ法

がある.

……

初めてn級を跳んだ場合、残りのn-n級にはf(n-n)種跳法

がある.
従ってf(n)=f(n−1)+f(n−2)+...+f(n−n)=f(0)+f(1)+...+f(n−1)
f(n-1) = f(n-1-1) + f(n-1-2) + … + f(n-1-n+1) = f(0) + f(1) + … + f(n-2)
従ってf(n)=2*f(n-1)
再帰出口:n=1の場合、ジャンプ法は1つしかありません.
Demo:

int jumpFloorII(int number) 
{
    if (number <= 0) return -1;
    else if (number == 1) return 1;
    return 2 * jumpFloorII(number-1);
}

 
矩形オーバーライドの問題
2*1の小さな矩形で横になったり、縦になったりして、より大きな矩形を覆うことができます.すみません、n個の2*1の小さい矩形で重ならずに1個の2*nの大きい矩形を覆って、全部で何種類の方法がありますか?
この問題は階段を跳ぶ問題と全く同じで、私たちは大きな矩形のnの側を考えるだけで、2の側は横に置いても、2つ置けばいいだけです.
Demoは同じです.