Coin Change(III) I want to solve it by three state coin change DP. But I am getting MLE, RTE. How can I solve it by this way?? Please help me. My code is here.
#include <bits/stdc++.h>
using namespace std;
int n,m,dp[101][101][1001];
int coin[101], number_coin[101];
set<int>S;
int M;
int call(int i, int taken_i, int make)
{
if(make>=1 && make<=M) S.insert(make);
if(make>M || i>n) return 0;
if(make==M) return 1;
if(dp[i][taken_i][make]!=-1)
return dp[i][taken_i][make];
int p1=0, p2=0;
if(taken_i>0)
{
p1=call(i,taken_i-1,make+coin[i]);
}
p2=call(i+1,number_coin[i+1], make);
dp[i][taken_i][make]=p1+p2;
//cout<<dp[i][taken_i][make]<<endl;
return dp[i][taken_i][make];
}
int main()
{
int t;
scanf("%d",&t);
int cas=0;
while(t--)
{
scanf("%d %d",&n, &m);
M=m;
for(int i=1; i<=n; i++)
{
scanf("%d",&coin[i]);
}
for(int i=1; i<=n; i++)
{
scanf("%d",&number_coin[i]);
}
memset(dp,-1,sizeof(dp));
int a=call(1,number_coin[1],0);
printf("Case %d: %d\n",++cas,S.size());
S.clear();
}
return 0;
}
Can you please tell what is this problem about? I cant open LightOJ
Sorry, undertansder bad the problems!!!
I think an O(M*N*T) solution could pass. The idea is just to maintain an array dp[current sum][2], where dp[s][i&1] += dp[s-x*a[i]][(i-1)&1] for every 0 <= x <= c[i]. But this solution is O(M*N*T*C[i]). But we can reduse it to O(N*M*T). We will maintain an array pref[current sum]. pref[s] = dp[s] + pref[s-a[i]]. So then dp[s]=pred[s]. Or simply we can change the formula to dp[s][i&1]=dp[s][(i-1)&1] + dp[s-a[i]][i&1].
P.S. if you dont know a&1 is the same as a%2.
I think that dp [s] [i&1] = dp [s] [(i-1)&1] + dp [s-a[i]] [i&1] is correct only if c[i] is unlimited because in your recurrence dp[s][i] depends on dp [s-a[i]] [i] which depends on dp [s-2*a[i]] [i] which itself depends on dp [s-3*a[i]] [i]. So dp [s][i&1] depends on dp [s-(c[i]+1)*a[i]] [i&1] too. Am I wrong?
Didn't realize that :d. Then I think it must be dp[s][i&1]=dp[s][(i-1)&1] + dp[s-a[i]][i&1] -dp[s-a[i]*c[i]][(i-1)&1].
Actually I am not understanding your talking. If you help me based on my code then it will be helpful for me. Please.
Send the link to the condition of the problem
Hey!! I am suggesting you the procedure I've followed!! Hope, it helps!!
This problem can be solved in O(n*m) time. where n=number of coins, m=amount.
Suppose, I want to check the money between 1 to 6. I have coins 2,3. 2 can be used for 2 times.
The moneys are 1,2,3,4,5,6,7,8,9. Suppose I want to start with coin 2. then I'll iterate through 2 to 9 to check which money I can make with this coin. Initially, You set dp[0]=1.//base case.
So, for 2 , starting from i=2, I can make 2 since dp[2-[present_coin]]==1, i.e, dp[0]=1. then set dp[2]=present coin.//since number of coins are limited, u will need this to check. now store 1 in an array since this is the 1st use of coin 2. _cnt array will store how many times a particular coin has been used to make a amount.
so, dp[2]=2. _cnt[2]=1.
now, for i=3, I can't make 3 since dp[3-[present_coin]]==0,i.e, dp[1]=0 and I couldn't make 1. then leave it. dp[3]=0. _cnt[2]=0.
for i=4, I can make 4 since dp[4-present_coin]==2, i.e dp[2]=2. Here is a matter, since dp[4-present_coin]==2 that means coin 2 has been made with a use of present coin. Since number of coins is limited so you have to check _cnt array to determine whether you can use present coin or you have already used max time.
since _cnt[2]=1 that means you have used present coin 1 time to make previous amount,2. and if you want to make 4 using present coin then you will used present coin for _cnt[2]+1=2 times.Since I can use coin 2 for max 2 times so, I can use present coin to make 4. dp[4]=2. _cnt[4]=_cnt[2]+1.//1 for using present coin another time.
Now, for i=5, I can't make 5 since dp[5-[present_coin]]==0,i.e, dp[3]=0 and I couldn't make 5 using present coin since coin 3 has not been made yet; then leave it. dp[5]=0. _cnt[5]=0.
For i=6, I can make 6 since dp[6-present_coin]==2, i.e dp[4]=2. Here is a matter, since dp[6-present_coin]==2 that means coin 4 has been made with a use of present coin. Since number of coins is limited so you have to check cnt array to determine whether you can use present coin or you have already used max time. Since cnt[4]=4 that means you have used present coin 2 times to make previous amount,4. and if you want to make 6 using present coin then you will used present coin for _cnt[4]+1=3 times,which is not allowed.Since I can use coin 2 for max 2 times so, I can't use present coin to make 6. dp[6]=0. _cnt6]=0.
The last case, i=6, is very important to understand.
"now, for i=3, I can't make 3 since dp[3-[present_coin]]==0,i.e, dp[1]=0 and I couldn't make 1. then leave it. dp[3]=0. _cnt[2]=0."
I think here is a correction. It should be "_cnt[3] = 0" in the place of "_cnt[2]=0". Isn't it?
And It would be helpful if anyone could give the explanation for the 2nd coin which value is 3.
if anyone needs problem description. Here is the link. (You don't need to login/register for that !!)
1233 – Coin Change (III)(http://lightoj.com/volume_showproblem.php?problem=1233&language=english&type=pdf)