✅ dp ✅ Bottom up

質問する

リンク

に答える

1.問題のアクセスと解決ロジック（解法）

3番目に現れる可能性のある数字は、i┅1 i-1 i┅1(すなわち、前の)数字が何であるかに依存する.
i−1i-1i−1iii0110,221,332,443,554,665,776,887,998
i,1 i−1 iは,1番目の数と同様に,i,2 i−2 iは,2番目の数が何であるかによって異なる.
つまり、すべての位置は前の数字によって影響を受けます.
i=0 i=0 i=0からi=n 1 i=n-1 i=n–1まで、前の数値を順番にチェックして状況の数を取得できますが、実行したプロセスが繰り返され、タイムアウトになります.
(「正解を10000000に分割し、残りの答えを出力します.」の場合は非常に多く、タイムアウトを招く可能性があります)
そのため、点火式を確立しなければならない.
定義

f(n,d)f(n,d)f(n,d)の長さはnであり、最後の数字はdの次数

である.

の答え
f(n,0)+f(n,1)+f(n,2)+...+f(n,9)f(n,0)+f(n,1)+f(n,2)+...+f(n,9)f(n,0)+f(n,1)+f(n,2)+...+f(n,9)

初期値
f(1,1)=f(1,2)=f(1,3)=...=f(1,9)=1f(1,1)=f(1,2)=f(1,3)=...=f(1,9)=1f(1,1)=f(1,2)=f(1,3)=...=f(1,9)=1
0で始まる次数がないので、f(1,0)=0 f(1,0)=0 f(1,0)=024579182

点火式
f(n,d)=f(n−1,d+1),(d==0)f(n,d)=f(n-1,d+1),(d==0)f(n,d)=f(n−1,d+1),(d==0)
f(n,d)=f(n−1,d−1),(d==9)f(n,d)=f(n-1,d-1),(d==9)f(n,d)=f(n−1,d−1),(d==9)
f(n,d)=f(n−1,d−1)+f(n−1,d+1),(0

初期値
1桁の場合は階段数が1つしかありません.

点火式
3番目の数字が決定された場合、i−1 i−1(すなわち、前)を用いて2番目の数字も決定される.
1、3番目の数の関係表を見て、点火式を導出します.

2.コード

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>

using namespace std;

int stair[101][10]; // stair[n][d] : 길이가 n(최대100),마지막 숫자가 d(0~9)인 계단수 개수

int main()
{
    int N, ans = 0;
    cin >> N;

    // 초기값 저장
    stair[1][0] = 0; // 0으로 시작하는 수는 계단수가 아니다.
    for (int i = 1; i <= 9; i++) // 한자리 수일 때는 계단수가 한가지(본인)밖에 없다.
    {
        stair[1][i] = 1;
    }

    for (int n = 2; n <= N; n++)
    {
        for (int d = 0; d <= 9; d++)
        {
            if (d == 0)
                stair[n][d] = stair[n - 1][d + 1] % 1000000000;
            else if (d == 9)
                stair[n][d] = stair[n - 1][d - 1] % 1000000000;
            else
                stair[n][d] = (stair[n - 1][d - 1] + stair[n - 1][d + 1]) % 1000000000;
        }
    }

    for (int d = 0; d <= 9; d++)
    {
        ans  = (ans + stair[N][d]) % 1000000000;
    }

    cout << ans % 1000000000 << "\n";

    return 0;
}

🔥 あふれ出る

for (int d = 0; d <= 9; d++)
{
    ans += (stair[N][d] % 1000000000);
}

ansに階段を10万の残りの部分に分けると、ドアを繰り返すことで増加し、10万を超える可能性があります.(オーバーフロー)
したがって、ans自体はANS+stairを10000000で割った残りの部分に変換される.

for (int d = 0; d <= 9; d++)
{
	ans  = (ans + stair[N][d]) % 1000000000;
}

ちなみに、アイエルツの範囲が広いlong longを使うのも一つの方法です.

3.時間複雑度分析

私たちはすべての状況を見つけます.
O(N)O(N)O(N)

4.問題の重要な部分

DP問題で重要なのは,点火式の導出である.
オプションはBootm Up(繰り返し文)で展開するか、Top Down(再帰)で展開するか