Computer_Science/leetcode/64-minimum_path_sum.c


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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];
}