Daily AtCoder # 40 in Python

Introduction

Last time Today I will do A ~ C of DP Contest

A problem

** Thoughts ** dp [i] is $ dp [i-1] + abs (h [i] -h [i-1]) or dp [i-2] + abs (h [i] -h [i-2]) $ Will be. It is calculated by updating these two minimum values.

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

dp = [0] * n  #I feel that inf is better

for i in range(1,n):
    if i == 1:
        dp[i] = abs(h[i]-h[0])
        continue
    dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]),dp[i-2]+abs(h[i]-h[i-2]))
print(dp[-1])

B problem

Problem

** Thoughts ** The difference from A is that the number of choices has changed from two to K, but only the part that takes min is increased accordingly.

n, k = map(int,input().split())
h = list(map(int,input().split()))

dp = [float('inf')] * n
dp[0] = 0
dp[1] = abs(h[1]-h[0])
for i in range(2,n):
    for j in range(k+1):
        if i - j < 0:
            continue
        dp[i] = min(dp[i-j]+abs(h[i]-h[i-j]),dp[i])
print(dp[-1])

C problem

Problem

** Thoughts ** Unlike A and B, dp [i-1] is involved in the choice of dp [i]. So, add one element of dp like dp [i] [j] to record what you chose with dp [i-1]. After that, calculate all three options and take the maximum value.

n = int(input())
abc = [list(map(int,input().split())) for _ in range(n)]

dp = [[0 for _ in range(3)] for _ in range(n+1)]

for i in range(1,n+1):
    for j in range(3):
        for k in range(3):
            if j == k:
                continue
            dp[i][k] = max(dp[i][k],dp[i-1][j] + abc[i-1][k])

ans = 0
for i in range(3):
    ans = max(ans,dp[n][i])
print(ans)

Summary

The name dp is cool, isn't it? I will do my best to master it. Let's do our best tomorrow's ABC! See you again, good night.