[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++

kotlin