白駿11057上り坂樹-node.js

このポスターは白準11057号の上り坂の木を描いています.質問リンク
コードはjavascriptで書かれています.

質問する

1.問題の説明

上り坂数とは、数字の位置が昇順に並ぶ数です.このとき、隣接する数が同じでも昇順に打つ.

[例]

2234と367811119は上り坂数です.

2232,3676,9111は上り坂数ではありません.

数の長さがNの場合、上り坂数を求めるプログラムを作成します.

数はゼロから始まることができます.

入力

第1行はN(1≦N≦1000)を与える.

しゅつりょく

出力1行目の長さNの上り坂数を10007の残りの部分で割った.

に答える

1.ロジック

3ビット数___の場合、各ビット数は、前のビット数のSTATEに従って決定され得る.したがって、この問題はDPによって解決することができる.
詳細な論理は、例によって説明されます.

2.ロジック

N=3の場合、可能な上り坂数を求める.
前述したように、各ビット数は、前の数字のSTATEに基づいて入力可能な数字を決定する.
したがって,n=1から部分和を求める.

[N =1]10ケース

0から9まで10種類のケースがあり、1桁であるためです.

0から9の場合はそれぞれ1つの場合を占めている.

DP中N=1の場合は、DP[0]として保存される.
DP[0] = [1,1,1,1,1,1,1,1,1,1]

[N =2]の55種類の場合

10の桁数は一日の桁数の値によって決まる.

0+0~9(10種)
1+1-9(9種)
2+2~9(8種類)
...
8+8~9(2種類)
9+9(1種)

DPでは、N=2の場合をDP[1]として保存する.
DP[1] = [10,9,8,7,6,5,4,3,2,1]

[N =3]220の場合

白の桁数は、前の桁数の値に基づいて入ることができる桁数を決定します.

0+00~99(55種)
1+11~99(45種)
2+22～99(36種類)
...
8+88~99(3種類)
9+99(1種)

N = 3の場合、DP[2]=[55,45,36,28,21,15,10,6,3,1]となる.N = 2の場合、DP[1]=[10,9,8,7,6,5,4,3,2,1].
このケースを表示すると、DP[2][0] = DP[2][1] + DP[1][0]と判断できます.
理由は.
DP[2][0] = 0 + 00~99//55
DP[2][1] = 0 + 11~99//45
DP[1][0] = 0 + 0~9//10
はい、DP[2][1]は、前の数が00~09のエンクロージャ、すなわちDP[1][0]を含まないためです!

DPでは、N=3の場合をDP[2]として保存する.
DP[2] = [55,45,36,28,21,15,10,6,3,1]

3.点火式

てんかしき
DP[i][j] = DP[i][j+1] + DP[i-1][j]

完全なコード

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

const DP = new Array(N+1);

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

for (let i = 1; i <= N; i++) {
	for (let j = 8; j >= 0; j--) {
		DP[i][j] = (DP[i][j+1] + DP[i-1][j]) % 10007;
	}
}

console.log(DP[N][0]);