白駿10844号簡単な階段数-Nodejs

同ポスターは、白準10844号の軽い階段水水泳を描いている.質問リンク
コードはjavascriptで書かれています.

質問する

問題の説明

階数:인접한 모든 자리의 차이가 1因数(EX.455656)

Nの場合、長さNの階段数をいくつ求める.

0で始まる数字は階段数ではありません.

入力

[첫째 줄] : N (1 ≤ N ≤ 100)

しゅつりょく

[첫째 줄]:正解%1億円

に答える

論理的説明

N=2の場合、可能な次数を考えてみましょう.
10、21、12、32、23、43、34、54、45、65、56、76、67、87、78、98があります.
これらの数字を見ると、10桁は事の数によって決まる単語です.일의 자리 수가 0の場合、1の違いが生じる自然数は1のみである.
逆に2부터 8까지 자연수自分の+1,-1の数字が出てくる.例えば、作業ビット数が8の場合、可能なステップ数は78,98である.일의 자리 수가 9の場合、1の違いが生じる自然数は8のみである.
このように、以前の数字がどのような値だったかによって、得られる答えが決まりました.つまり、先桁(部分和)を求めるには、DP로 풀이だけでよい.

例の説明

N=3の場合は例で説明します.


上の表から見ると、Nが3の場合、可能な組み合わせは32個あります.[N=1]일 때1～9の間には様々な自然水があります.0は自然数ではなく、不可能です.[N=2]일 때

j=0の場合、自分+1人10(「1」+「0」)しかできません.

j=1の場合、自分+1人21(「2」+「1」)しかできません.

jが2~8の間の自然数の場合、自己+1,-1とすることができる.

jが9の場合、自分-1人89(「8」+「9」)しかいません.

[N=3]일 때

j=0の場合
dp[3][0]はdp[2][1](210) + '0'

j=1～8の場合
jが1〜8のとき、観察の組み合わせは、dp[3][j] = dp[2][j-1] + dp[2][j+1]であると判定される.

j=9の場合
dpが確認できる[3][9]はdp[2][8](78, 98) + '9'

j=0、9の場合、それぞれdp[i][j]=dp[i-1][j-1]、dp[i][j]=dp[i-1][j+1となる.
逆に、j=1~8の場合、dp[3][j]=dp[2][j-1]+dp[2][j+1]となる.
インデックス-1と10の要素がないためです.
したがって,論理を点火式として以下に示す.

てんかしき

JSの比較演算子を用いて,上の論理を次の点化式として表すことができる.
てんかしき
DP[i][j] = DP[i-1][j-1] || 0 + DP[i-1][j+1] || 0
(0 ≤ j ≤ 9)

完全なコード

const input = require('fs').readFileSync('/dev/stdin').toString();
const N = Number(input);

const DP = new Array(N)

for (let i=0; i<N; i++) {
    DP[i] = new Array(10).fill(0)
}

for (let i=1; i<=9; i++) {
    DP[0][i] = 1;
}

for (let i=1; i<N; i++) {
    for (let j=0; j<=9; j++) {
        DP[i][j] = (DP[i-1][j-1] || 0) + (DP[i-1][j+1] || 0) % 1000000000;
    }
}

const result = DP[N - 1].reduce((acc, curr) => {
  return (acc + curr) % 1000000000;
}, 0);

console.log(result);