I need help on Light Oj problem 1233(Coin Change (III)).
Problem Link
I came up with a solution of O(T*N*M*C[i]). Here is my idea: Let dp[i][j] is true if we can make value j using first i coins. So, dp[i][j]=true if dp[i-1][j-k*x] is true for (0<=k<=c[i-1]) where i>0, x is the current coin and (j-k*s>=0). Initially dp[0][0]=true since we can make 0 using 0 coins. Final result will be sum of dp[n][i] where (1<=i<=m).
My Submission
. But this solution is slow. How to make it faster? How to solve this problem using O(T*N*M) time complexity?
bool dp[105][100005];
void solve() {
T can be 20 in this case u must make 105 * 100005 operation 20 times -> 210 010 500 — its to slow. memset(dp,false,sizeof(dp)); change this to make false only the area where u work, mb by for
for(int i = 0; i <= n; i++){
for(int j = 0; j <= m; j++)
}
but i still dont know O(T*N*M) solution
and u can use dp[100001] instead of dp[105][100005];
Mb so
I concoct some optimise u can make set instead of dp[105][100005] and every time view it rather than this large array
i make it so
I can't understand how set will optimise my complexity. set has logarithmic factor. I think it will make complexity worse. Am I missing something?
You every time checking from 0 to m, if u will use set it will be less Example: ur silution
0 1 2 3 4 5 6 7 8 9 10
1) 1 1 0 0 0 0 0 0 0 0 0
2) 1 1 1 0 0 0 0 0 0 0 0
3) 1 1 1 1 1 0 0 0 0 0 0
4) 1 1 1 1 1 1 1 1 1 0 0
with set it will be work so
0 1 2 3 4 5 6 7 8 9 10
1) 1 1
2) 1 1 1
3) 1 1 1 1 1
4) 1 1 1 1 1 1 1 1 1
with dp u check the cells where value = 0, with set no, but yes it is logarithmic