Bottom up Dp problem ( Help post)

→ Обратите внимание

До соревнования
Educational Codeforces Round 173 (Rated for Div. 2)
39:12:06
Зарегистрироваться »

→ Трансляции

aryanc403

До начала 41:22:06

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя 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

# 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
6 лет назад
7

Комментарии (6)

Показать архивные | Написать комментарий?

daihan

6 лет назад, # |

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

→ Ответить

MZuenni

6 лет назад, # ^ |

← 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);
    } 
}

→ Ответить