the dp problem: stamp Given a set of N stamp values (e.g., {1 cent, 3 cents}) and an upper limit K to the number of stamps that can fit on an envelope, calculate the largest unbroken list of postages from 1 cent to M cents that can be created.
I try to use dp in the following way, but get wrong on test 9, my method is:
let dp[i][j] be the max value W that can be made from 1 to W, with the condition that we use first i types of coin and at most j coins to make the total value. then anwser is dp[N][K].
for(int i=1;i<=N;i++)for(int j=0;j<=K;j++)
{
long long maxlen=dp[i-1][j];
long long k=1;
while(k<=j){
int next= k * a[i];
if(next>maxlen+1)break;
else{
maxlen=max(maxlen,k*a[i]+dp[i-1][j-k]);
k++;
}
}
dp[i][j]=maxlen;
}
fout<<dp[N][K]<<endl;
it wrong for test case: K(max coin to use)=6, N(size of coins set)=10 , coins={1 2 9 31 255 480 4 15 63 127 } my output is 242,while anwser is 720.
I try hard, but I can't figure out why this method is wrong. Anyone please take a minute to help me with this dp problem, thank you so much in advance!