Bottom up Dp problem ( Help post)

daihan's blog

By daihan, 7 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

# include < bits/stdc++. h >

using namespace std;

int n,q,i,j;

int dp[2000000];

int flag[2000000];

int recursion(int N) {

// cout<<N<<endl;

if(N==0)
    return 0;

if(dp[N]!=-1)
    return dp[N];

int x=recursion(N-1)+1;
int y=2147483647;

for(int i=2; i*i<=N; i++)
    if(N%i==0)
        y=min(y,recursion(N/i)+1);

dp[N]=min(x,y);

return dp[N];

}

int main() {

memset(dp,-1,sizeof(dp));

scanf("%d",&q);

while(q--) {

    scanf("%d",&n);
    printf("%d\n",recursion(n));

}

return 0;

}

daihan
7 years ago
7

Comments (6)

Show archived | Write comment?

daihan

7 years ago, hide # |

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

→ Reply

MZuenni

7 years ago, hide # ^ |

← Rev. 4 →

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