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

How to construct the bottom up solution(DP) for this question?
Автор anh1l1ator, 9 лет назад, По-английски

In general , I am sometimes stuck at creating bottom up for a question... So I want to know how to think while constructing bottom up... For example while I was able to think the recursive solution for this question, I am simply unable to construct bottom up for this question(and not able to understand the solutions of others too)...Problem linkLink Link to my memoized solution Solution

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

i think that for this problem writing bottom up dynammic programming is much easier than writing top down. 

for(int i=2;i<=n;i++){
        int v = A[i] ;
        for(int j=1;j<=10000;j++){
          if(DP[i-1][j]){
            DP[i][__gcd(v,j)] += DP[i-1][j] ;
        }
        DP[i][j] += DP[i-1][j] ;
}
→ Ответить