这是一道动态规划的题目,就是走格子,然后算出最少过路费的题目。
这道题目的初始化需要先做第一个点,然后从它出发第一行第一列。
状态转移方程式和循环公式都比较简单。
初始化initialization:
min_sum[0][0] = grid[0][0];
for (int i = 1; i < m; ++i) min_sum[i][0] = min_sum[i-1][0] + grid[i][0];
for (int i = 1; i < n; ++i) min_sum[0][i] = min_sum[0][i-1] + grid[0][i];
状态转移方程式optimum-value function:
min_sum[i][j] = min(min_sum[i-1][j], min_sum[i][j-1]) + grid[i][j];
循环公式recurrent formula:
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
}
}