1.问题

用什么数字标记？

今天写 #120. 三角形最小路径和 的时候，用记忆化搜索的方式。其中需要用一个 int 整型 memo[i]，来标记某点是否被计算过值；如果没有计算过，将计算后的值储存在 memo[i] 中。

我将 memo[i] 初始化为 -1，遍历时，如果发现该点上的 memo[i] 为 -1，则说明没有计算过，并将计算后的值储存在该点上的 memo[i] 中。

**问题来了：**计算后的值可能会是 -1，也可能会是 0，那我应该用什么数字去标记是否计算过呢？

2.无穷大

答案是，可以用 无穷大 来标记，即 int 的最大值：INT_MAX = 0x7fffffff。

因为 0x7fffffff 在正常数据运算中基本不可能出现。

3.新问题

那如何将数组全部初始化为无穷大？

我们知道，将数组清零，我们可以用 memset 。

int memo[100];
memset(memo, 0, sizeof(memo));

如果要将数组初始化为无穷大，是不是可以 memset(memo, 0x7fffffff, sizeof(memo)); ？答案是不行！

memset(memo, 0x7fffffff, sizeof(memo)); 最后执行的结果是 数组每个数都等 -1。因为 memset 是按照字节赋值的。

4.memset 原理

memset 是按照字节赋值的。举几个例子

1. memset(memo, 0, sizeof(memo)); 是对 每个字节 都赋值为 0；以64位 int 为例，四个字节分别赋值为 0（最后该数字还是等于0）。
2. memset(memo, -1, sizeof(memo)); 是对 每个字节 都赋值为 -1，-1 的补码是 1111 1111 1111 1111 1111 1111 1111 1111，存入 1 字节就是 1111 1111（高位舍弃），每个字节都是 1111 1111 ，那四个字节就是 1111 1111 1111 1111 1111 1111 1111 1111，所以该 int 数字还是 -1
3. memset(memo, 0x7fffffff, sizeof(memo)); 是对 每个字节 都赋值为 0x7fffffff，正整数的补码是本身，存入 1 字节就是 ff （高位舍弃），每个字节都是 ff，那四个字节就是 ffffffff， ffffffff 是 -1 的补码。（计算机打印十六进制时，打印的补码；打印十进制时，打印的是原码）。

所以 int数组 不可以用 memset 来初始化为 0x7fffffff。

那该怎么办呢？用 0x3f3f3f3f 代替 0x7fffffff。

5.0x3f3f3f3f

0x3f3f3f3f 和 0x7fffffff 是一个数量级的，也可以作为无穷大。

好处在于：

• 0x3f3f3f3f 可以满足 无穷大 + 无穷大 = 无穷大 的设定。

• 0x3f3f3f3f 可以用 memset 来初始化。

为什么 0x3f3f3f3f 可以用 memset 来初始化呢？

memset(memo, 0x3f3f3f3f, sizeof(memo)); 对每个字节都赋值为 0x3f3f3f3f，所以一个字节为 3f （高位舍弃），四个字节连在一起就是 0x3f3f3f3f，和原值大小一样。

6.新发现

在leetcode写#279. 完全平方数时，经测验发现，用 0x7fffffff 整个程序运行时间 200+ms，用 0x3f3f3f3f 运行时间 300+ms。

所以如果不使用 memset 的时候，用 0x7fffffff。

vector<int> a(n, 0x7fffffff);    // 运行更快。
vector<int> b(n, 0x3f3f3f3f);