# 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 O(S) space solution using DP with tabulation# (bottom-up)defcc_tab_super_opt(a,S):N=len(a)tab=[1ifs==0else0forsinrange(S+1)]n,s=1,0whilen!=N+1:ifs==S+1:n,s=n+1,0else:ifa[n-1]<=s:tab[s]+=tab[s-a[n-1]]s+=1returntab[S]
Comments (0)
HTTPSSSH
You can clone a snippet to your computer for local editing.
Learn more.