Why is this a dynamic programming problem?


  • 0
    W

    why is

     minPathSum[i, j] = MIN( minPathSum[i-1, j] + grid[i,j],   minPathSum[i, j-1] + grid[i,j] )
    

    why can't there be a path leading to (i,j) that's not the minPathSum but because grid[i,j] is small so the sum up to (i,j) is minimum?

    Thanks.


  • 1
    C

    Although, I didn't understand what you mean...

    I'll try to explain what kind of problem can be handled by DP.

    There are two requirements:

    1. the optimization of the problem is based on the optimization of its sub-problem.

      e.g. minPathSum[i,j] is optimiezed based on the optimization of minPathSum[i-1,j] and so on.

    2. sub-problem can be solved alone without the influence of bigger problem.

      e.g. solving minPathSum[i-1, j] didn't need or influenced by grid[i,j] at all.

    Satisfying the above requirements, this problem can be solved by DP.

    (Note that refine the split of problem can convert the problem to be DP solved. e.g. TSP problem)


  • -1
    R

    its a DP because you are re-using stuffs (minpath[i-1][j] and all) in your final computations..
    but the point i want to put here is that..you can't expect to easily get away by greedy approach (looking at min values and moving ahead), hence you need to compute min path to all the vertices and then compute min path of the last block using those pre computed vertices. (although we waste a lot of compute but it reaches optimal solution only this way).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.