# input: a[0..N) array of distinct positive integers, N>=0, and S# output: number of ways that S can be obtained with an unlimited# amount of coins with denominations in a[0..N)## O(NS) time and space solution using DP with tabulation (bottom-up)defcc_tab(a,S):N=len(a)tab=[[Noneforsinrange(S+1)]forninrange(N+1)]forsinrange(S+1):tab[0][s]=1ifs==0else0n,s=1,0whilen!=N+1:ifs==S+1:n,s=n+1,0else:tab[n][s]=tab[n-1][s]ifa[n-1]<=s:tab[n][s]+=tab[n][s-a[n-1]]s+=1returntab[N][S]
Comments (0)
HTTPSSSH
You can clone a snippet to your computer for local editing.
Learn more.