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
Everything looks great to me but the initialization of
dp[1][j] = 0
, it should bedp[0][j] = 0
and if you are iterating from (m — n +i > j) you should be returningdp[n][m]
try these once.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.
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]$$$
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.
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.