简介
Python 中的正负无穷为: float('inf') 和 float('-inf'). (inf 全称为 infinity)
正负无穷的应用
作为比较大小时的初值. 需要选出最大值, 使用负无穷, 反之, 使用正无穷.
使用 LeetCode 64 题来详细说明.
题目描述
给定一个包含非负整数的 m x n, 请找出一条从左上角到右下角的路径, 使得路径上的数字总和为最小.
说明: 每次只能向下或者向右移动一步.
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小.
题目相关内容讲解
每个点只能由上或左到达, 因此该点的最小值 = 左和上中的最小值 + 自身值. 使用代码表示为 min(left, up), 使用这个函数的隐含条件是 left 和 up 必须存在.
因此可能会写出如下代码. ( dp[row][col-1] 代表左值, dp[row-1][col] 代表上值 )
image
如果使用正无穷, 那么代码将变得整洁, 易读.
image
用求 up 的过程来详细讲解下, 当 row - 1 <= 0, 则当前节点为第一行节点, 没有上值. 如果赋值为正无穷, 使用 min, 一定会挑选另一个.
题目完整代码参考
image
