天池 在线编程 最小的行程（动态规划）

样例 1:
输入:
1 2 3
4 5 6
7 8 9
输出:
12
解释:
最短的路径为:1->4->7, 返回12.

样例 2:
输入:
7 1 12 1
2 3 4 2
1 10 2 6
Output:
4
解释:
最短的路径为:1->2->1, 返回 4.

class Solution {
public:
    /**
     * @param matrix: 
     * @return: Return the smallest path
     */
    int smallestPath(vector<vector<int>> &matrix) {
        // Write your code here
        int m = matrix.size(), n = matrix[0].size();
        vector<int> dp = matrix[0];
        for(int i = 1; i < m; i++) 
        {
            vector<int> temp(n, 0);
            int prevmin;
            for(int j = 0; j < n; j++)
            {
                prevmin = dp[j];
                if(j-1 >= 0)
                    prevmin = min(prevmin, dp[j-1]);
                if(j+1 < n)
                    prevmin = min(prevmin, dp[j+1]);
                temp[j] = matrix[i][j] + prevmin;
            }
            swap(dp, temp);
        }
        return *min_element(dp.begin(), dp.end());
    }
};