leetcode64-Minimum Path Sum(최소 경로 및)

문제 설명:
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
m * n의 격자를 지정하십시오. 격자에 마이너스가 아닌 숫자가 있습니다.로봇은 왼쪽 상단에서 오른쪽 하단으로 내려가야 한다. 매번 아래로 또는 오른쪽으로 한 위치만 이동할 수 있고 총계가 가장 작은 경로를 찾아 최소치를 되돌려준다.
이 문제는 leetcode62-Unique Paths와 유사합니다.
문제 해결:
전형적인 동태 기획 문제.동적 기획의 세 가지 요소: 문제의 단계, 각 단계의 상태와 전 단계에서 후 단계로 전환되는 점차적인 관계.점차적인 관계는 작은 문제에서 비교적 큰 문제 간의 전환이어야 한다. 이런 측면에서 보면 동적 기획은 종종 점차적인 프로그램으로 실현할 수 있지만 점차적인 것은 앞에 저장된 하위 문제의 해를 충분히 이용하여 중복 계산을 줄일 수 있기 때문에 대규모 문제에 있어 점차적인 것은 비교할 수 없는 장점이 있다. 이것도 동적 기획 알고리즘의 핵심이다.동태적인 기획의 이 세 가지 요소를 확정하면 전체적인 해답 과정은 하나의 최우선 의사결정표로 묘사할 수 있다. 최우선 의사결정표는 2차원 표이다. 그 중에서 줄은 의사결정의 단계를 나타내고 열은 문제의 상태를 나타낸다. 표에 기입해야 하는 데이터는 일반적으로 이 문제가 특정한 단계의 특정한 상태에서 최우수값(예를 들어 가장 짧은 경로, 가장 긴 공공 서열, 최대 가치 등)에 대응한다. 표를 작성하는 과정은 점차적인 관계에 따라1행 1열부터 행이나 열을 우선하는 순서로 차례대로 표를 작성하고 마지막으로 전체 표의 데이터에 따라 간단한 취사나 연산을 통해 문제의 최우선을 구한다.
먼저 추이 관계를 찾아낸다. 예를 들어 모든 칸에 저장할 기점을 설정하고 j의 최소 경로와 2차원 그룹은 MPS[i][j]이고 추이 공식은 다음과 같다.

MPS[i][j] = Min（MPS[i-1][j]，MPS[i][j-1]）+ grid[i][j]；

격자 i, j의 MPS 값은 두 가지 출처가 있을 수 있다. 왼쪽 격자 i, j-1 또는 위쪽 격자 i-1, j;이 두 출처의 비교적 작은 MPS 값을 취하고 현재 칸의 값grid[i][j]을 더하면 결과입니다.!!!
왼쪽 위에서 오른쪽으로 내려가기 때문에 우리는 이중 순환을 이용하여 교체 계산을 할 수 있다. 외부 순환은 행위 단위, 내부 순환은 열을 단위로 한다. 이렇게 하면 이미 계산된 단계, 상태를 이용하여 현재 칸의 결과를 계산할 수 있다. 왜냐하면 매번 어떤 칸을 계산할 때 왼쪽 칸과 위쪽 칸의 결과가 이미 계산되었기 때문이다. 이것도 동적 계획이 귀속보다 빠른 원인이다.

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> minPathSum(grid);
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(i==0 || j==0)
                {//           
                    if(i==0) minPathSum[0][j] += minPathSum[0][j-1];
                    else minPathSum[i][0] += minPathSum[i-1][0];
                }
                else
                {//  [i][j] minPathSum      :    [i][j-1],     [i-1][j].
                 //      ，         grid[i][j]     
                    minPathSum[i][j] = min(minPathSum[i][j-1], minPathSum[i-1][j])+grid[i][j];
                }
            }
        }
        return minPathSum[m-1][n-1];
    }
};

공간 복잡도는 O(m*n), 시간 복잡도는 O(m*n)이다.