![](/style/images/good.png)
![](/style/images/bad.png)
Need help in a dp problem
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
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;
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:
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:
I hope this would help you.
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK