[Algorithm]動的プログラミング問題-金鉱、整数三角形、退砂

金鉱

T = int(input())
while T:
    n, m = map(int, input().split())
    data = list(map(int, input().split()))
    dp = []
    count = 0
    for i in range(n):
        dp.append(data[count:count + m])
        count += m

    for k in range(1, m):
        for j in range(n):
            # 첫번째 줄
            if i == 0:
                dp[j][k] = dp[j][k] + max(dp[j + 1][k - 1], dp[j][k - 1])
            # 마지막줄
            elif i == n - 1:
                dp[j][k] = dp[j][k] + max(dp[j - 1][k - 1], dp[j][k - 1])
            else:
                dp[j][k] = dp[j][k] + max(dp[j + 1][k - 1], dp[j][k - 1], dp[j - 1][k - 1])

    print(max(dp[n - 1]))

3つのケース
1)最初の行->左上隅と左上隅
2)最後の行->左下と左下
3)残り->左下左上

せいすうさんかくけい

n = int(input())

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

for i in range(1, n):
    for j in range(len(data[i])):
        if j == 0:
            data[i][j] = data[i][j] + data[i - 1][j]
        elif i == j:
            data[i][j] = data[i][j] + data[i - 1][j - 1]
        else:
            data[i][j] = data[i][j] + max(data[i - 1][j], data[i - 1][j - 1])

print(max(data[n - 1]))

ざっと計算して、ルールを見つけました.

退社する

n = int(input())

t = []
p = []

for i in range(n):
    T, P = map(int, input().split())
    t.append(T)
    p.append(P)
dp = [0] * (n + 1)
for j in range(n - 1, -1, -1):
	# 시간 안 넘으면
    if t[j] + j <= n:
        dp[j] = max(dp[j + 1], p[j] + dp[j + t[j]])
    else:
        dp[j] = dp[j + 1]

print(dp[0])

時間を超えなければ.
dp[j] = max(dp[j + 1], p[j] + dp[j + t[j]])
翌日に利益を得たほうが、今日仕事を終えてから仕事を終えたほうがいいです.
時間を超えると.
dp[j] = dp[j + 1]
翌日