Блог пользователя daihan

Bottom up Dp problem ( Help post)
Автор daihan, 6 лет назад, По-английски

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
  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    6 лет назад, # ^ |
    ← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    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);
    } 
}
    → Ответить