每日leetcode第0034天 0063. Unique Path II

这是上一道题目的升级版。也是一道入门的动态规划走地图题。

初始化就是第一行和第一列,一遇到障碍物开始后面都是0,要把循环写得漂亮就得像这样写。

状态转移方程分为障碍物和非障碍物两种了,所以这里我用了Conditional Operator,这样写在一行里会好看一些,哈哈哈。

初始化initialization:
for (int i = 0; i < m && map[i][0] == 0; i++) path[i][0] = 1;
for (int i = 0; i < n && map[0][i] == 0; i++) path[0][i] = 1;

状态转移方程式optimum-value function:
path[i][j] = map[i][j] ? 0 : path[i – 1][j] + path[i][j – 1];

循环公式recurrent formula:
for (int i = 1; i < m; ++i) {
for (int j = 1; j < n; ++j) {
}
}



关于樊轶群

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

发表评论

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