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?
