PythonでJOI難易度5を埋める #16

D - シルクロード (Silk Road)

考えたこと
愚直に求めようとすると,それぞれの町で2通りあるので計算量が2^{n}以上になって間に合わなさそうなので,DPを使って解く.
普通にDPするだけ
町の数\times日程のDPテーブルを作る

n, m = map(int, input().split())
d = [int(input()) for _ in range(n)]
c = [int(input()) for _ in range(m)]

dp = [[float('inf')] * (n+1) for _ in range(m + 1)]
for i in range(m + 1):
    dp[i][0] = 0

for i in range(1, m+1):
    for j in range(1, n + 1):
        dp[i][j] = min(dp[i][j], dp[i-1][j], dp[i-1][j-1] + d[j - 1] * c[i - 1])

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