5
cb219
3y

Tldr:
Can't fucking figure out why I'm the only one who can't solve a DP problem in code, when me and friends use the same idea and no one knows why only mine doesn't work...

We are given a task to solve a problem using DP. My friends write their code with the same idea as a solution. Copying the code is not allowed. I follow the same idea but my code won't work. Others look into it, in case they find errors. They can't find any.

The problem (for reference):
Given a fixed list of int's a = (a_1,a_2,...,a_n) and b = (b_1,b_2,...,b_n), a_i and b_i >= 0, a.length == b.length
We want to maximize the sum of a_i's chosen. Every a_i is connected with the b_i at the same index. b_i tells us how many indexes of a we have to skip if choosing the corresponding a_i, so list index of b_i + b_i's value + 1 would be the position of the next a_i available.

The idea:
Create a new list c with same length as a (or b).
Begin at the end of c and save a_n at the same position in c. Iterate backwards through c and at each position add the max value of all previously saved values of c (with regards to the b_i-restriction) with the current a_i, else a_i + 0 if the b_i-resctriction goes beyond the list.
Return the max value of c.

How does that not work for me but for the others?? Funny enough, a few given samples work with my code. I'm questioning my coding ability...

Comments
  • 10
    What is DP? Double Penetration?
  • 4
    @neeno That was my assumption. I may be wrong
  • 3
    @neeno
    Dynamic programming. Also know as "find the point of recursion"
  • 0
    DP is dynamic programming which involves storing previously computed values for quick access so they don’t have to be recomputed
  • 3
    I feel ya. I had the same problem all semester trying to solve kattis problems (many of them also DP). My best strategy for this is typing the solution out again and all of a sudden it magically works 🤷🏻‍♀️
  • 0
    @d-fanelli Is this the same thing as memoization.

    You can even add memoization to a Python function with a decorator and never have to touch the function itself. :)
  • 0
    A little update:
    I've found the bug, as I accessed the wrong list at a crucial point. Nevertheless an interesting problem regarding time:
    I calculate everything in 1 function and return the correct result to just print it out. Runs into timeout, but runs perfectly on my machine.
    Some friend's code does the exact same, just more split up. I call a function in which I iterate through the list and solve every index and return the max value, he iterates through the list and at every index calls a function where he solves the specific index. After that loop he searches the max value in the list.
    Why does his approach not time out?
Add Comment