lintcode 1612 · 最小的行程 【动态规划 中等 vip】

题目

https://www.lintcode.com/problem/1612文章来源地址https://uudwc.com/A/dbe91

给定一个二维矩阵，找到从上到下的最小路径。只能向左下，下，右下移动


1.所有的元素都是正整数

样例
样例 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.

思路

动态规划：矩阵为n*m,  dp[n][m], n=0时，第一行的值和原数组相同。
第二行开始，每个值依赖于他的上面，左上，右上，
三个值中最小那个和自己相加。最后结果取dp[n-1]中最小的一个

代码

public class Solution {
    /**
     * @param matrix: 
     * @return: Return the smallest path
     */
    public int smallestPath(int[][] matrix) {
           //动态规划
        int n = matrix.length, m = matrix[0].length;
        int[][] dp = new int[n][m];

        for (int i = 0; i <m ; i++) { //先填充第一行
            dp[0][i] = matrix[0][i];
        }

        for (int i = 1; i <n ; i++) {
            for (int j = 0; j <m ; j++) {
                int top = dp[i-1][j];
                int leftTop = Integer.MAX_VALUE; //左上
                if(j>0){
                    leftTop = dp[i-1][j-1];
                }

                int rightTop = Integer.MAX_VALUE; //右上
                if(j<m-1){
                    rightTop = dp[i-1][j+1];
                }

                dp[i][j] = matrix[i][j]+ Math.min(top,Math.min(leftTop,rightTop));
            }
        }

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i <m ; i++) {
            ans =Math.min(ans,dp[n-1][i]);
        }
        return ans;
    }
}