leetcode筆記：Minimum Path Sum

一. 題目描述

Given a m  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 的網格，每個格子裡有一個非負整數，找到一條從左上角到右下角的路徑，使其經過的格子數值之和最小，每一步只能向右或向下走。

動態規劃，可以使用一個m*n的矩陣來存儲到達每個位置的最小路徑和。每個位置的最小路徑和應該等於自身的值加上左側或者上面兩者中的極小值。這樣很容易寫出狀態轉移公式：

f[i][j] = min(f[i-1][j], f[i][j-1]) + grid[i][j]

三. 示例代碼

#include 
#include 

using namespace std;

class Solution {
public:
    int minPathSum(vector > &grid) 
    {
        if (grid.size() == 0) return 0;
        const int m = grid.size();
        const int n = grid[0].size();
        int f[m][n];
        f[0][0] = grid[0][0];
        for (int i = 1; i < m; i++) 
            f[i][0] = f[i - 1][0] + grid[i][0];

        for (int i = 1; i < n; i++) 
            f[0][i] = f[0][i - 1] + grid[0][i];

        for (int i = 1; i < m; i++)
        {
            for (int j = 1; j < n; j++) 
            {
                f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j];
            }
        }
        return f[m - 1][n - 1];
    }
};

四. 小結

這是一道典型的動態規劃題，使用動態規劃求解問題，最重要的就是確定動態規劃三要素：問題的階段、每個階段的狀態以及求出從前一個階段轉化到後一個階段之間的狀態轉移公式，當然該題也可以使用遞推來完成，不過效率可能就沒有動規高。