関連タグ

動的計画法、C言語

問題の説明

三段階の階段を登る問題です。ある子供が階段を登っているとします。階段はn段あり、その子供は一度に1段、2段、または3段を登ることができます。このとき、子供が階段を登る方法の総数を計算するアルゴリズムを実装してください。結果は非常に大きくなる可能性があるため、1000000007で剰余を取ってください。

解法の考察

これは基本的な動的計画法の問題です。DPの一般的なアプローチに従い、n=1、n=2、n=3、およびn>3の4つのケースに分けて考えます。

n=1の場合、最後の1段だけを登る方法しかありません。したがってf(1)=1です。

n=2の場合、最後に1段を登る方法と最後に2段を登る方法の2通りがあります。よってf(2) = f(1) + 1 = 2です。

n=3の場合、最後に1段、2段、3段を登る3通りの方法があります。よってf(3) = f(2) + f(1) + 1 = 4です。

n>3の場合、n段目に到達する方法はf(n)通りあります。最後に踏む段数によって、「最後に1段を登る」「最後に2段を登る」「最後に3段を登る」の3つの場合に分けられます。それぞれの場合はf(n-1)、f(n-2)、f(n-3)の方法数に対応し、f(n) = f(n-1) + f(n-2) + f(n-3)となります。

以下のコードのように実装できます：

int waysToStep(int n){
    if(n == 1){
        return 1;
    }
    else if(n == 2){
        return waysToStep(1) + 1;
    }
    else if(n == 3){
        return waysToStep(2) + waysToStep(1) + 1;
    }
    else{
        return (waysToStep(n - 1) + waysToStep(n - 2) + waysToStep(n - 3)) % 1000000007;
    }
}

実行するとタイムアウトが発生します 😦

他の解答を参考にして、以下のように改善します：

n=4のとき、f(4) = f(3) + f(2) + f(1) n=5のとき、f(5) = f(4) + f(3) + f(2) ... n=nのとき、f(n) = f(n-1) + f(n-2) + f(n-3)

明らかに、各nについての方法数は直前の3つの値に依存しており、これらはすべて直前の計算で利用されています。そのため、4要素の配列kindを使用して途中の計算値を保持します。具体的には：

int waysToStep(int n){
    if(n < 3){
        return n;
    }
    if(n == 3){
        return 4;
    }
    // 段数が1つ増えるたびに、直前の3段の方法の合計が新しい方法数となる
    int *kind = (int*)malloc(sizeof(int) * 4);
    kind[0] = 1;
    kind[1] = 2;
    kind[2] = 4;
    for(int i = 3; i < n; ++i){
        kind[3] = (kind[0] + kind[1] + kind[2]) % 1000000007;
        for(int j = 0; j < 3; ++j){
            kind[j] = kind[j + 1];
        }
    }
    return kind[3];
}

実行するとスタックオーバーフローが発生します 😦

3つの最大値が1000000006である場合、それらの和がint型の範囲を超える可能性があるため、kind配列の型をlong longに変更すると正しく動作します 😀

コード

int waysToStep(int n){
    if(n < 3){
        return n;
    }
    if(n == 3){
        return 4;
    }
    // 段数が1つ増えるたびに、直前の3段の方法の合計が新しい方法数となる
    long long *kind = (long long*)malloc(sizeof(long long) * 4);
    kind[0] = 1;
    kind[1] = 2;
    kind[2] = 4;
    for(int i = 3; i < n; ++i){
        kind[3] = (kind[0] + kind[1] + kind[2]) % 1000000007;
        for(int j = 0; j < 3; ++j){
            kind[j] = kind[j + 1];
        }
    }
    return kind[3];
}