Pythonで解く【初中級者が解くべき過去問精選 100 問】(039 - 045 動的計画法：ナップザック DP亜種) - Qiita

1. 目的 初中級者が解くべき過去問精選 100 問をPythonで解きます。 すべて解き終わるころに水色になっていることが目標です。 本記事は「039 - 045 動的計画法：ナップザック DP亜種」です。 2. 総括 目標となるdpテーブルを実際に書けると問題は解けますが、テーブルをイメージできないとなかなか解くことが難しいです。 3. 本編 039 - 045 動的計画法：ナップザック DP亜種 039. JOI 2011 予選 4 - 1 年生 回答 N = int(input()) num = list(map(int, input().split())) dp = [[0] * (N-1) for _ in range(21)] for i in range(21): if i == num[0]: dp[i][0] = 1 for j in range(1, N-1): fo