diff options
Diffstat (limited to 'Computer_Science/leetcode/64-minimum_path_sum.c')
| -rw-r--r-- | Computer_Science/leetcode/64-minimum_path_sum.c | 20 |
1 files changed, 20 insertions, 0 deletions
diff --git a/Computer_Science/leetcode/64-minimum_path_sum.c b/Computer_Science/leetcode/64-minimum_path_sum.c new file mode 100644 index 0000000..f9d7a50 --- /dev/null +++ b/Computer_Science/leetcode/64-minimum_path_sum.c @@ -0,0 +1,20 @@ +#define MIN(a, b) ((a) > (b) ? (b) : (a)) + +int minPathSum(int** grid, int gridRowSize, int gridColSize) { + int dp[gridRowSize][gridColSize]; + + int i, j; + + dp[0][0] = grid[0][0]; + + for(i = 1; i < gridColSize; i++) + dp[0][i] = dp[0][i - 1] + grid[0][i]; + for(i = 1; i < gridRowSize; i++) + dp[i][0] = dp[i - 1][0] + grid[i][0]; + + for(i = 1; i < gridRowSize; i++) + for(j = 1; j < gridColSize; j++) + dp[i][j] = MIN(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]; + + return dp[gridRowSize - 1][gridColSize - 1]; +} |