anh1l1ator's blog

How to construct the bottom up solution(DP) for this question?
By anh1l1ator, 11 years ago, In English

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

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, hide # |
← Rev. 5  
Vote: I like it 0 Vote: I do not like it

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] ;
}
→ Reply