Quiz
https://yukicoder.me/problems/no/314
Submit
https://yukicoder.me/submissions/330500
他の人の解法
- dp[i][j] : i番目まで見たとき、ケンの数が j である場合の数
解法
- 私は、直前2つの状態を見れば遷移が決まることから、
- dp[i][j][k]
- i 番目まで見たとき
- j 前回に出した手
- k 今回に出した手
- 手
- 0 : ケン
- 1 : パ
- とした
- サイズ dp[N_MAX][2][2]
- 例：dp[2][0][1]
- 2番目まで見たとき、ケン・パで終わる場合の数
動的計画法
- 過去2つ、3つの状態から次の遷移先が決まる問題は多い
- 状態の持ち方は上記のように2つある
- j に統計値（今回で言えばケンの数）をもたせる
- 2つ、3つ程度なら配列の次元を増やす
