【Educational DP Contest】EDPC-A-Frog1【Python】

問題
解答
1. 方針
2. 解答
その他
1. 解答・解説記事一覧

問題

A – Frog 1 (atcoder.jp)

解答

方針

・ dp[i]をi番目の足場でのコストの最小値とする

・遷移式：dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]))

解答

コード・コメント

#入力
n = int(input())
H = list(map(int,input().split()))
#DP配列を作成。最小値を求める問題だが、DP配列の各要素でコストを加算していくので0で初期化
dp = [0]*(n)

#dp[0]、つまり最初の位置では高さは変わらないのでコストは0となる。上記の通り0で初期化しているので操作は不要
#n-1回繰り返す(dp[1]～dp[n-1])
for i in range(1,n):
　　#iが1(2番目の足場)の場合、まだ1つしか足場を進んでいないので、2つ前の足場からのコストを求める計算(dp[i-2]+abs(H[i]-H[i-2])ができない
　　#そのため、H[1]-H[0]を求める
    if i == 1:
        dp[i] = abs(H[i]-H[0]) #H[i]-H[0]としているが、H[1]-H[0]でも良い
　　#iが2以上(3番目以降の足場)では、1つ前の足場からのコストと2つ前の足場からのコストを比較して小さい方をdp[i]として記録する
    else:
        dp[i] = min(dp[i-1]+abs(H[i]-H[i-1]),dp[i-2]+abs(H[i]-H[i-2]))
#DP配列の最後尾を出力
print(dp[-1])

#入力

n = int(input())

H = list(map(int,input().split()))

#DP配列を作成。最小値を求める問題だが、DP配列の各要素でコストを加算していくので0で初期化

dp = [0]*(n)

#dp[0]、つまり最初の位置では高さは変わらないのでコストは0となる。上記の通り0で初期化しているので操作は不要

#n-1回繰り返す(dp[1]～dp[n-1])

for i in range(1,n):

　　#iが1(2番目の足場)の場合、まだ1つしか足場を進んでいないので、2つ前の足場からのコストを求める計算(dp[i-2]+abs(H[i]-H[i-2])ができない

　　#そのため、H[1]-H[0]を求める

if i == 1:

dp[i] = abs(H[i]-H[0]) #H[i]-H[0]としているが、H[1]-H[0]でも良い

　　#iが2以上(3番目以降の足場)では、1つ前の足場からのコストと2つ前の足場からのコストを比較して小さい方をdp[i]として記録する

else:

dp[i] = min(dp[i-1]+abs(H[i]-H[i-1]),dp[i-2]+abs(H[i]-H[i-2]))

#DP配列の最後尾を出力

print(dp[-1])

コード

n = int(input())
H = list(map(int,input().split()))

dp = [0]*(n)
for i in range(1,n):
    if i == 1:
        dp[i] = abs(H[i]-H[0])
    else:
        dp[i] = min(dp[i-1]+abs(H[i]-H[i-1]),dp[i-2]+abs(H[i]-H[i-2]))

print(dp[-1])

n = int(input())

H = list(map(int,input().split()))

dp = [0]*(n)

for i in range(1,n):

if i == 1:

dp[i] = abs(H[i]-H[0])

else:

dp[i] = min(dp[i-1]+abs(H[i]-H[i-1]),dp[i-2]+abs(H[i]-H[i-2]))

print(dp[-1])

その他

解答・解説記事一覧

EDPCの解答・解説記事一覧

【Python】Educational DP Contest 解答・解説記事一覧【EDPC】

ABCの解答・解説記事一覧

【Python】AtCoder Beginner Contest 解答・解説記事一覧