めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

DP演習（問題案）

テンプレートに慣れるための問題

以下の問題について、DP のテンプレートに従ってコードを書いてください。また、それぞれの計算量（ $O(N), O(N^2)$ など）を答えてください。

[テンプレート]

# N: データ数

dp = [None] * (N+1)

dp[1] = xxxx # 1個の場合の答えを自力で考えて入力する

for n in range(2, N+1):
  dp[n] = xxxxx # dp[1] ... dp[n-1] の情報を使って n 個の場合の答え dp[n] を計算する

print(dp[N])

[問題1]

N 個の整数の最大値を求める

[問題2]

N 個の整数の平均値を求める

ヒント
$\displaystyle {\rm dp[n-1]} = \frac{1}{n-1}\sum_{i=1}^{n-1}A_i \ \Rightarrow\ \sum_{i=1}^{n-1}A_i=(n-1) {\rm dp[n-1]}$

[問題3]

ヒント
・dp[n] : n 番目までの足場に対する問題の答え
・dp[1] に加えて、dp[2] も個別に計算するとコードがすっきりする

[問題4]

ヒント
$O(N^2)$ でも間に合う

中級問題

ここの問題は、テンプレートそのまま、というわけには行きません。解くべき問題を拡張する、リスト dp[ ][ ] を埋めていく順序をよく考える、などの工夫をしてください。

[問題5]

ヒント
・条件付きの問題に置き換える
・dp[n][x] : x の部分でどのような条件を指定するべきか？

[問題6]

ヒント
・dp[a][b] : a 個の 'a' と b 個の 'b' で表現できる場合の数
・dp[a][b] = 先頭が 'a' の場合の数 + 先頭が 'b' の場合の数
・K 番目の文字列の先頭は 'a' と 'b' のどちら？
（解答例）

[問題7]

ヒント
・n = 1, 2, 3 程度の場合を手で計算してみる
・dp[n][m] : 1 〜 n のコインでちょうど m 枚が表の確率
（解答例）

[問題8]

ヒント
・dp[a][b][c] :（寿司 1 個 a 皿、寿司 2 個 b 皿、寿司 3 個 c 皿）の時の残り回数（期待値）
・何らかの変化が発生するまでの試行回数（期待値）は、N / (a + b + c)
・変化後の状態は、dp[a-1][b][c]、dp[a+1][b-1][c]、dp[a][b+1][c] のどれか。それぞれの割合は、a : b : c
・dp のリストを埋める順番をよく考える
（解答例）

状態価値関数

[問題9]

ヒント
・状態価値関数の考え方をこちらで学習する
・「先手の得点 - 後手の得点」をお互いに最大化／最小化しようとするものと考える
・先手の状態価値関数と後手の状態価値関数を別々のリスト dp1[ ][ ]、dp2[ ][ ] に用意して、それぞれを交互に埋めていくと考えてもよい
（解答例）

区間DP

[問題10]

ヒント
・区間DPをこちらで学習する
・考えてる幅の最後の要素について、これとペアにするべき要素はどれ？
（解答例）