thePointyEnd's blog

I struggle with 3D DP problems. Can you recommend some good 3-D DP problems to practice?
By thePointyEnd, history, 4 weeks ago, In English

Everytime I get a 3-D DP problem, I'm able to figure out that the problem can be solved using 3-D DP, I'm also able to define the DP sometimes, but I'm never able to define the base cases and therefore can't solve the problem. Can you please recommend some Standard/Good 3-D DP problems that I can practice?

For Eg. There was this problem: An array of n integers is given. Each element of the array is an integer value > 0. You have to divide the array in 2 parts such that the difference between the sizes of the two parts cannot be greater than 1 and the difference between the summation of elements of the two parts is minimised.

How do I solve this problem?

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think I have seen that problem on atcoder. I think it was C and was solved via bitmasking as the constraints were really low. Could you link to the problem or mention the constraints if so. Thanks.

→ Reply
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Constraints were not low as far as I can remember. Also I don't have the link as this was asked to me in a test.

    → Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

104772G - Game of Nim

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

best time to buy and sell stocks 3 & 4 (Leetcode), but ig thats an easy problem of 3D DP

→ Reply