[LeetCode]--64. 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.

题目很容易读懂，就是找到一条路径从左上到右下并且使得路径上的所有值加起来最小。

思路就是用一个二维数组记录最小的值，每次比较之后相加本身。

public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] val = new int[m][n];
        val[0][0] = grid[0][0];
        for (int i = 1; i < m; i++)
            val[i][0] = grid[i][0] + val[i - 1][0];
        for (int i = 1; i < n; i++)
            val[0][i] = grid[0][i] + val[0][i - 1];
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                int tmp = val[i - 1][j] >= val[i][j - 1] ? val[i][j - 1]
                        : val[i - 1][j];
                val[i][j] = grid[i][j] + tmp;
            }
        }
        return val[m - 1][n - 1];
    }

另外一种就是一维数组的方法，其实跟这个是一样的，就是少用一点内存，但是没有上面的好理解。

/**
     * 一维数组的方法
     * @param grid
     * @return
     */
    public int minPathSum1(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[] val = new int[n];
        val[0] = grid[0][0];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0 && j > 0) {
                    int tmp = val[j] >= val[j - 1] ? val[j - 1] : val[j];
                    val[j] = grid[i][j] + tmp;
                } else if (j > 0) {
                    //处理第一行
                    val[j] = grid[i][j] + val[j - 1];
                }
                else if (i > 0) {
                    //处理第一列
                    val[0] = grid[i][j] + val[0];
                }
            }
        }
        return val[n - 1];
    }