[LeetCode] 64. Minimum Path Sum

轉自LeetCode

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.

<Solution>

這題和 Unique Path 滿像的，但這次是要求走過路線上的數值總和的最小值

還是用 dp 的觀念， dp[i][j] += min(dp[i-1][j], dp[i][j-1])

那有幾點可以注意

• 因為題目有說，只能向右或向下，所以 row 0 : dp[0][c] += dp[0][c-1], 1<= c < n

•  同理，col 0 : dp[r][0] += dp[r-1][0], 1<= r < m

• 不用再另外準備一個二維陣列來存，用題目給的 grid 就可以了

code 如下
c++

	class Solution {
	private:
	int ans, m, n;
	public:
	int minPathSum(vector<vector<int>>& grid) {
	const int m = grid.size(), n = grid[0].size();
	//> first row
	for(int c = 1; c < n; c++) {
	grid[0][c] += grid[0][c-1];
	}
	//> first col
	for(int r = 1; r < m; r++) {
	grid[r][0] += grid[r-1][0];
	}
	//> find min sum
	for(int r = 1; r < m; r++) {
	for(int c = 1; c < n; c++) {
	grid[r][c] += min(grid[r-1][c], grid[r][c-1]);
	}
	}
	return grid[m-1][n-1];
	}
	};

view raw minPathSum.cpp hosted with ❤ by GitHub

kotlin

	class Solution {
	fun minPathSum(grid: Array<IntArray>): Int {
	val row = grid.size
	val col = grid[0].size
	for(r in 1 until row) {
	grid[r][0] += grid[r-1][0]
	}
	for(c in 1 until col) {
	grid[0][c] += grid[0][c-1]
	}
	for(r in 1 until row) {
	for(c in 1 until col) {
	grid[r][c] += Math.min(grid[r-1][c], grid[r][c-1])
	}
	}
	return grid.last().last()
	}
	}

view raw minimum_path_sum.kt hosted with ❤ by GitHub