I tried solving this problem of CSES Problemset: Coin Combinations II
This is the solution I came up with using Recursive DP :-
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
const ll MOD = 1e9 + 7;
int n, k, a, b, c, d, x, y;
vector<int> arr(101);
vector<vector<int>> dp(1000001, vector<int>(101, -1));
int ways(int target, int index) {
if(target == 0) return 1;
if(index == n || target < 0) return 0;
if(dp[target][index] != -1) {
// cout << target << ' ' << index << "\n";
return dp[target][index];
}
else dp[target][index] = ((ways(target - arr[index], index))%MOD + (ways(target, index+1))%MOD)%MOD;
return dp[target][index];
}
int main() {
ios::sync_with_stdio(false);
cout.tie(0); cin.tie(0);
cin >> n >> k;
for(int j = 0; j<n; j++) cin >> arr[j];
cout << ways(k, 0);
return 0;
}
Most of the tutorials used Iterative DP for the solution but I am not able to see why this recursive DP solution won't work. This solution gives TLE on 7/15 test cases.
Can someone please help me with this
you are declaring global DP table which is of the size 100 million which takes time, and second thing If one of your coin denominations is very small (like 1), the recursion may go very deep (up to 1e6 levels in the worst case), which is inefficient compared to an iterative approach.
So there's no way to make it work with recursive DP?
May be No!
try using arrays instead of vectors
bro it's given 1e6 and 1e2 , you gotta do it in 1sec(exactly 1e8 operations allowed) . Recursive solution takes auxiliary stack space, do it through bottom up .
I don't believe that this is solvable with memoization.
I wrote a good recursive implementation, and it also fails with time limit and runtime error (presumably because of recursive calls (10^8 (function calls)* (two saved calls)8 bytes == 800Mb >500Mb).
This is one of my gripes with CSES. Sometimes, how you write the solution matters a lot. For instance, if you use Fenwick Tree(faster) vs iterative Segment Tree(slower), recursive Segment Tree (slowest). There's some practical knowledge that is gained but I feel like this tends to defeat the fact the solutions have the correct complexity. It can make you think that there's a better complexity, when it's an implementation issue.