動的計画法（すごろく）

問題

$ N $ 個のマスのすごろくがあり、スタートから順に $1$ から $N$ までの番号が付けられています。

このすごろくでは、マス$ i(1 \leqq i \leqq N -1) $ にいるとき、次の２種類の行動のうち一方を選ぶことができます。

🔹マス $A_i$ に進み、スコア100を得る。
🔹マス $B_i$ に進み、スコア150を得る。

ゴールにたどり着くまでに得られる合計スコアの最大値を出力してください。

なお、ゴールから遠ざかる移動をすることはありません。

[制約]
🔹$ 2 \leqq N \leqq 100000 $
🔹$ i + 1 \leqq A_i \leqq B_i \leqq N $

解き方・ソースコード

マス $i$ から移動するときの１つ先の行動として考えられるものは次の２種類です。

🔹スコア100を得てマス $ A_i $ に進む
🔹スコア150を得てマス $ B_i $ に進む

マス $i$ まで進んだ時点で得られるスコアの最大値を $dp[i]$ とするとき、本題の答えである $dp[N]$ の値は以下のように計算することができます。

$dp[1] = 0$ とし $i=1,2,…,N$ の順に以下のことを行う。
🔹$dp[A_i]$の値を $max(dp[A_i],dp[i]+100)$ に更新する
🔹$dp[B_i]$の値を $max(dp[B_i],dp[i]+150)$ に更新する

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#--------- 入力例 ----------
N = 7
A = [2, 4, 4, 7, 6, 7]
B = [3, 5, 6, 7, 7, 7]
#---------------------------
# 配列の初期化
dp = [ -(10 ** 9) ] * (N + 1)
dp[1] = 0

# 動的計画法
for i in range(1, N):
    dp[A[i - 1]] = max(dp[A[i - 1]], dp[i] + 100)
    dp[B[i - 1]] = max(dp[B[i - 1]], dp[i] + 150)
print(dp)

# 出力
print('解：', dp[N])

[実行結果]

[-1000000000, 0, 100, 150, 250, 250, 350, 500]

解： 500

合計スコアの最大値は500であることが確認できました。