3

Need help in a dp problem

 2 years ago
source link: http://codeforces.com/blog/entry/96571
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Hello guys I was trying to solve Coin Combination — 2 in cses . I used iterative dp and this is the best I could write but it's giving TLE in 3 cases.Can someone help me out?Is memory optimization needed?

https://cses.fi/problemset/task/1636

Problem Link

https://cses.fi/paste/d24ee9c3d89dff062eeede/

Here's my solution

96 minutes ago, # |

Atleast paste the question link. and try int instead of long long

  • 93 minutes ago, # ^ |

    I have used int instead of long long, see carefully,I wrote : typedef int ll; in my template

83 minutes ago, # |

Here is My code ...... Use Long long int to be on safe side

void Here_We_Go() { int n,x; cin >> n >> x; vector v(n); for (int i = 0; i < n;i++) cin >> v[i]; vector dp(x + 1, 0); dp[0] = 1;

for(int e : v )
{
    for (int i = e; i <= x;i++)
    {
        (dp[i] += dp[i - e]) %= mod;
    }
}
cout << dp[x] << endl;

40 minutes ago, # |

Rev. 2  

+1

In the Coin Combinations I problem, let's assume that dp[k] is the number of ways that we can create a sum of k from given coins. It is clear that dp[0] = 1, which means we always can create sum = 0 with 0 coin.

Thus, to do this task, iterate sum value from 1 to X, then for each sum value, we find all combinations possible with given n coins, each combination of that coin is caculated in to the dp[] once. The code will look like this:

Coin Combinations I

In Coin Combinations II problem, let's recall the define of dp[k]: number of ways we can create sum of k from given coins where each coin has infinite count. For example, if there is a coin with value '2' and we want to create sum of 14, there are possible sum could be created: 2,4,6,8,10,12 and 14

As can be seen, there is a little different from the previous problem: with each coin, we have to find all possible value could be created from that coin, with each combination of that coin could be caculated in to dp[] more than once. Then the code should look like this:

Coin Combinations II

I hope this would help you.


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK