lvisbl_'s blog

Help debug dynamic programming problem!
By lvisbl_, history, 3 weeks ago, In English

Recently, I have encounter this dynamic programming problem and I can not debug where I have problem, I used forward DP style and I have checked the transition and base case. Please help me to look at it, I'm so frustrating. Thank in advance.

Problem link: leetcode

My code:

code

Updated fix my problem: my for loop only run until i = n, but the final dp state which is dp[n + 1][m + 1] can be reached from dp[n + 1][m] => My for loop should run till n + 1 so this relaxation can happen.

fixed
  • Vote: I like it
  • -2
  • Vote: I do not like it

»
3 weeks ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Everything looks great to me but the initialization of dp[1][j] = 0, it should be dp[0][j] = 0 and if you are iterating from (m — n +i > j) you should be returning dp[n][m] try these once.

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

    This is actually backward DP, I'm intended to use forward DP, but for this problem backward DP seem more intuitive. Thank you! Btw I have fixed forward DP following phantrongnghia510 suggestion.

    → Reply
»
3 weeks ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

You should consider all valid costs in all final valid states of $$$i$$$: $$$min_j(dp[n + 1][j])$$$ for all $$$j\in [n + 1, m + 1]$$$ since we have just advertised the cost upwards but yet to finalize any optimal cost at $$$dp[i][m + 1]$$$

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

    Thank this is the expected answer, but how do you visualize the problem to get the optimal cost. I think I have "visited" all the states that can reach dp[n + 1][m + 1], and use all those states to "optimize gradually" dp[n + 1][m + 1], hence my expectation that when I reach dp[n + 1][m + 1], it should have been optimized in its optimal cost. But turn out, it is not.

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

    Ah, I finally got it, the state dp[n + 1][m + 1] can be reached from dp[n + 1][m] but my for loop run until i = n then dp[n + 1][m + 1] never be optimized by dp[n + 1][m]. Thank you so much for pointing it out.

    → Reply
»
3 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

sorry for bumping this up again but i have a stupid doubt.

after reading the editorial about flattening $$$factories$$$'s limit of repairs (if factory is on position $$$pos$$$ and can repair $$$limit$$$ robots, just add $$$pos$$$ in our flattened array $$$limit$$$ times) and doing a simple DP on indices,

i tried doing a 3 state $$$DP(i,j,f_{j})$$$ where the last state is just $$$f_{j}$$$ (limit of factory at j index , this does not require flattening like in the editorial). each time we do a $$$repair$$$ transition, mutate the value of $$$f_j$$$ and after computing the value for this transition, for $$$skip$$$ transition, revert back to the original value of $$$f_j$$$.

this did got AC , but shouldn't this cause some sort of side effect or is it okay to mutate state like this and then revert.

$$$ f[j][1] = f[j][1] -1\newline repair = |r[i] - f[j][0] | + F(i+1,j)\newline f[j][1] = f[j][1] +1\newline $$$
$$$ skip = F(i,j+1) \newline DP(i,j,f_{j}) = min(repair,skip) $$$


My Code

PROBLEM LINK

→ Reply