최저 비용 경로

Question

질문 -

비 음수 가득 M 행 N 그리드 주어 그 경로상의 모든 수의 합을 최소화하는 하단 왼쪽 상단에서 경로를 찾기.

참고 : 만 나는 이것이 일반적인 문제입니다 알고 너희들의 대부분의 문제뿐만 아니라 동적 프로그래밍을 알 것

시간

에 어느 시점에 하나 아래로 또는 오른쪽으로 이동할 수 있습니다. 여기에 재귀 코드를 시도하고 있지만 올바른 출력을 얻고 있습니다. 내 재귀 코드에서 누락 된 부분은 무엇입니까? 필자는 반복적이거나 동적 인 프로그래밍 방식을 원하지 않습니다. 나 혼자서 만들려고 노력하고있어.

잘못된 출력을 표시합니다.

예 - 대답은 3

감사와 같이 곳은 2로 출력을 제공

1 2 
1 1 

.

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