![見出し画像](https://assets.st-note.com/production/uploads/images/92640266/rectangle_large_type_2_d19947861d1fba0c855f3ef588e7a359.png?width=800)
動的計画法
復習を記録します。
問題①
![](https://assets.st-note.com/img/1670129881786-Lepc0uxPhv.png?width=800)
![](https://assets.st-note.com/img/1670129925521-kozspP6gs4.png?width=800)
解答コード
# 入力
N = int(input())
H = list(map(int, input().split()))
# 動的計画法
dp = [ None ] * N
dp[0] = 0
for i in range(1, N):
if i == 1:
dp[i] = abs(H[i - 1] - H[i])
if i >= 2:
v1 = dp[i - 1] + abs(H[i - 1] - H[i]) # 1 個前の足場からジャンプするとき
v2 = dp[i - 2] + abs(H[i - 2] - H[i]) # 2 個前の足場からジャンプするとき
dp[i] = min(v1, v2)
# 答えの出力
print(dp[N - 1])
問題②
![](https://assets.st-note.com/img/1670130369201-roUmT0PAAS.png?width=800)
![](https://assets.st-note.com/img/1670130406521-PqZdXYfwST.png?width=800)
解答コード
# 入力
N = int(input())
# 動的計画法
dp = [ None ] * (N + 1)
print(dp) # [None, None, None, None, None]
for i in range(N + 1):
if i <= 1:
dp[i] = 1
else:
dp[i] = dp[i - 1] + dp[i - 2]
print(dp) # [1, 1, 2, 3, 5]
# 答えの出力
print(dp[N]) # 入力した要素のインデックスに入っている数を出力。
以上になります。
この記事が気に入ったらサポートをしてみませんか?