「典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～ 」をPythonで解く - u++の備忘録2月下旬に「典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～ 」の前半7問をPythonで解きました。ABCのD問題で時折出題されるDPの感覚をザックリと掴むことができました。 qiita.com 1 ナップサック DP とは 問題 1: 最大和問題 2 ナップサック問題 問題 2: ナップサック問題 3 部分和問題とその応用たち 問題 3: 部分和問題 問題 4: 部分和数え上げ問題 問題 5: 最小個数部分和問題 問題 6: K個以内部分和問題 問題 7: 個数制限付き部分和問題 1 ナップサック DP とは 問題 1: 最大和問題 n = int(input()) a = list(map(int, input().split())) # input # == # 3 # 7 -6 9 # == # dp[0] = 0 dp = [0]
