daihan's blog

Bottom up Dp problem ( Help post)
By daihan, 6 years ago, In English

Here is the problem link : https://www.hackerrank.com/challenges/down-to-zero-ii/problem

I used bottom up dp , but still getting stack overflow runtime error for input 1000000 . Can anyone help me , to point out where is wrong in my code :

code
  • Vote: I like it
  • +3
  • Vote: I do not like it

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

Is this problem impossible to solve with Bottom up DP ? I solved using top down dp , using queue .

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

    for $$$N=0$$$ you return $$$n$$$? shouldn't this be $$$0$$$?

    This is bottom up, gets accepted and its more or less in $$$O(n\sqrt{n})$$$:

    vector<int> res(1000001, 1000001);
res[0] = 0;
for (int i = 0; i < 1000001; i++) {
    res[i + 1] = min(res[i + 1], res[i] + 1);
    for (int j = 2; i * j < 1000001 && j <= i; j++) {
        res[i*j] = min(res[i*j], res[i] + 1);
    } 
}
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      This is $$$O(n\cdot log(n))$$$, as it can be written as $$$\sum_{i=1}^n\frac{n}{i} \simeq n \cdot ln(n) = O(n \cdot log(n))$$$

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

      Yeah, it should be 0. But still it overflow on 1000000

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

        and you probably want to initialize $$$dp$$$ with $$$0$$$ and not $$$-1$$$ ?

        → Reply