每日leetcode第0035天 0064. Minimum Path Sum

这是一道动态规划的题目,就是走格子,然后算出最少过路费的题目。

这道题目的初始化需要先做第一个点,然后从它出发第一行第一列。

状态转移方程式和循环公式都比较简单。

初始化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) {
}
}



关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。