最小コスト経路

Question

質問 -

は非負数で満たされたM×N個のグリッドが与えられると、そのパスに沿ってすべての数値の和を最小に左上から右下へのパスを見つけます。

注：あなたが唯一の私は、これは一般的な質問です知っているとあなたたちのほとんどは、質問だけでなく、その動的なプログラミングを知っているだろう

時間

に任意の時点でいずれかの下または右に移動することができます。私はここで再帰的なコードを試していますが、正しい出力を得ています。私の再帰コードには何がありませんか？私は反復的または動的プログラミングのアプローチを望んでいません。私は自分自身で構築しようとしています。

不正な出力を示します。

例 -

1 2 
1 1 

答えは3

おかげであるように、それはどこ2として出力を提供します。

def minPathSum(self, grid): 
    """ 
    :type grid: List[List[int]] 
    :rtype: int 
    """ 
    def helper(i,j,grid,dp): 
     if i >= len(grid) or j >= len(grid[0]): 
      return 0 
     print grid[i][j] 

     return grid[i][j]+min(helper(i+1,j,grid,dp),helper(i,j+1,grid,dp)) 
    dp = [[0] * len(grid[0]) for i in range(len(grid))] 
    val = helper(0,0,grid,dp) 
    print dp 
    return val 

Answer 1

グリッドの端から落ちたときに0を返すのは正しいとは限りません。それは、あなたが成功したように見えます。だから私はあなたが誤って報告している2は左上の1と左下の1であり、それに続いてグリッドの底から落ちる「成功した」と考えています。

if at right or bottom edge: 
    there is only one direction to go, so 
    return the result of going in that direction 
else you do have options, so 
    return the minimum of the two choices, like you do now