When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

RationalDeveloper's blog

By RationalDeveloper, history, 3 years ago, In English

I have trying to solve a lot of DP problem but I feel stuck. I can solve most of greedy problem. Any advice

  • Vote: I like it
  • -17
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If you are beginner in DP , I would suggest you practice Recursive DP first. Almost all DP problems you see until 1700-1800 rating can be easily solved with recursive version.

Still if you want to learn iterative, I think writing the transitions on paper helps a lot.

For example, Suppose recursive version is,
inside func(i,j):
DP[i][j] = func(i+1,j+1) + func(i+2,j+1);

I generally convert that right most term into i... like

DP[i-2][j-1] = func(i-1,j) + func(i,j);
=> DP[i-2][j-1] = DP[i-1][j] + DP[i][j]
=> DP[i][j] = DP[i-2][j-1] -DP[i-1][j]

Now I have a formula to use iterative dp using for loop.

PS:This is just personal opinion. There may be better way to figure out transitions. But I learnt it this way. :P

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    thank you so much for replying. really appreciate. I will try them in recursion.Before I was only trying iterative.

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      Add Ashishgup to your friendlist and refer his solutions for problems you are trying to solve. He almost always solves using recursive and you can see his solutions to learn.