Sandom_Rhuffle's blog

Need Help on Light Oj problem 1233!
By Sandom_Rhuffle, history, 5 years ago, In English

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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

bool dp[105][100005];

void solve() {

memset(dp,false,sizeof(dp));

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++)

dp[i][j] = 0;

}

but i still dont know O(T*N*M) solution

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I concoct some optimise u can make set instead of dp[105][100005] and every time view it rather than this large array

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i make it so

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

        → Reply