syuntoku14の進捗

進捗を書きなぐります

AOJでPythonに慣れる(4問目)

問題
Coin Changing Problem

所感
動的計画法入門
ポロック予想も同じ解法でできる(先にコイン問題やっとけばよかった)

コード

def main():
    n,m=map(int,input().split())
    c=list(map(int,input().split()))
    dp=list(range(n+1))
    k=0
    while k<len(c):
        for i in range(n+1-c[k]):
            dp[i+c[k]]=min(dp[i+c[k]],dp[i]+1)
        k+=1
    print(dp[n])

if __name__=="__main__":
    main()