【Python】DP(動的計画法)で次元を減らすテクニック【AtCoder】 - Qiita

import itertools,sys def I(): return int(sys.stdin.readline().rstrip()) def LI(): return list(map(int,sys.stdin.readline().rstrip().split())) ############################# N = I() p = LI() dp = [0]*10001 #0:その点数存在しない、1:その点数存在する dp[0] = 1 for i,j in itertools.product(range(1,N+1),range(10001)[::-1]): pi = p[i-1] if j-pi>=0: dp[j] = max(dp[j],dp[j-pi]) #選んだ場合 #dp[j] = max(dp[j],dp[j]) #選ばなかった場合→不要 p