質問する

ある動物園には横に2つ、横にNつのケージがあり、以下のようになっています.

この動物園にはライオンが住んでいて、ライオンをかごに閉じ込めたとき、横に縦に置くことはできません.この動物園のトナカイ師はライオンの安置問題に頭を悩ませている.
動物園のトナカイ師が頭を悩ませないように、2*N配列のライオンの数を知るプログラムを作成しましょう.ライオンが1匹も配置されていない場合でも、1つの場合の手段で打つことができます.

入力

第1行は我々のサイズN(1≦N≦100000)を与える.

しゅつりょく

1行目にライオンが置かれている場合は、残りの数字9901を出力します.

I/O例

// 입력
4
// 출력
41

に答える

まず考えがDP問題に分かれていたのですぐに思いつきました
N=1の場合
イメージ
この3つのケースがあります.

N=2の場合
XXの下まで行けるのはXX XO OXです.(3種類!)
OXの下まで行ける場合はXX XO(2種類!)
XO以下の場合はXXOX(2種類!)
XXの場合は3種類、OX、XOの場合は2種類あります.
これにより、3の個数と2の個数=>[3の個数、2の個数]が格納された配列と
この配列を使用して、3個の数+2個の数%9901を格納する配列を作成しました.3個と2個の数が多すぎて、番号タイプの範囲を超えています.ううう

こうして描くと、ルールが見つかりました.
dp[i]=dp[i-1]*2+d[i-2]が見えます.

コード#コード#

let input = `4`.trim();
// input = require('fs').readFileSync('/dev/stdin').toString().trim()
input = +input;

const dp = [0, 3, 7];

for (let i = 3; i <= input; i++) {
  dp[i] = (dp[i - 1] * 2 + dp[i - 2]) % 9901;
}
console.log(dp[input]);