刘强东
今天，一封《致光明村乡亲们的拜年信》刷屏了。
信中的内容除了常规的春节祝福以外，还提到了会给村民们送来品种繁多的年货礼物，60 岁以上的长辈，还将额外得到 1 万元现金，而当年在校的老师们，则每人可得 10 万元。
时间是 2025.1.7，落款人是刘强东。
其实关于「刘强东要给村里 60 岁以上老人发钱」的事儿，早在前几周就开始发酵，只不过颇具仪式感的通知，则是今天才来到。
刘强东的故事，相信大家都不陌生。
当年他上大学时（28 年前），全村人为他凑了 500 元和 76 个鸡蛋作为学费和生活费，这个行为对刘强东来说意义重大，他也曾多次在公开场合提到此事，因此刘强东任何时刻以任何形式对乡亲们表达感激之情，我都不会感到意外。
只不过，如果能够勿忘初心，对自己底层一线员工（尤其是快递员）再好点就更好了。
对此，你怎么看？此时此刻是不是想成为东哥（物理上）的亲人？
...
回归主题。
来一道和「腾讯」相关的算法题。
题目描述
平台：LeetCode
题号：464
在 "100 game" 这个游戏中，两名玩家轮流选择从 到 的任意整数，累计整数和，先使得累计整数和达到或超过 的玩家，即为胜者。
如果我们将游戏规则改为 “玩家不能重复使用整数” 呢？
例如，两个玩家可以轮流从公共整数池中抽取从 到 的整数（不放回），直到累计整数和 >= 。
给定两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家是否能稳赢则返回 true ，否则返回 false 。假设两位玩家游戏时都表现 最佳 。
示例 1：
输入：maxChoosableInteger = 10, desiredTotal = 11
输出：false
解释：
无论第一个玩家选择哪个整数，他都会失败。
第一个玩家可以选择从 1 到 10 的整数。
如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。
第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.
同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。
示例 2:
输入：maxChoosableInteger = 10, desiredTotal = 0
输出：true
示例 3:
输入：maxChoosableInteger = 10, desiredTotal = 1
输出：true
提示:
二维博弈论 DP（TLE）
这是一道博弈论 DP 的题，为了方便，我们使用 来表示 ，使用 来表示 。
由于 数据范围为 ，且每个数只能选一次，我们可以使用一个二进制数 来表示 范围内的被选择的数的情况：二进制表示中 的位置代表数已被选择，否则代表尚未选择。
首先朴素二维状态表示相对容易想到：定义 为当前已被选择的数为 ，轮数为 时，「原始回合的先手」能否获胜（ 代表能， 代表不能），其中 从 开始，通过 的奇偶性可知是原始回合的先手还是后手。
设计递归函数来实现「记忆化搜索」，函数 int dfs(int state, int tot, int k) 表示当前状态为 ， 对应累计和， 代表轮数，最终答案通过判断 dfs(0, 0, 0) 是否为 来得知。
转移过程中，如果发现当前回合的决策，能够直接使得累积和超过 ，说明当前回合玩家获胜；或者如果当前决策能够导致下一回合的玩家失败的话，当前回合玩家也获胜，否则当前玩家失败。
代码：
class Solution {
int n, t;
int[][] f = new int[1 << 20][2];
// 1 true / -1 false
int dfs(int state, int tot, int k) {
if (state == ((1 << n) - 1) && tot < t) return -1;
if (f[state][k % 2] != 0) return f[state][k % 2];
int hope = k % 2 == 0 ? 1 : -1;
for (int i = 0; i < n; i++) {
if (((state >> i) & 1) == 1) continue;
if (tot + i + 1 >= t) return f[state][k % 2] = hope;
if (dfs(state | (1 << i), tot + i + 1, k + 1) == hope) return f[state][k % 2] = hope;
}
return f[state][k % 2] = -hope;
}
public boolean canIWin(int _n, int _t) {
n = _n; t = _t;
if (t == 0) return true;
return dfs(0, 0, 0) == 1;
}
}
C++ 代码：
class Solution {
public:
int n, t;
vector<vector<int>> f;
int dfs(int state, int tot, int k) {
if (state == (1 << n) - 1 && tot < t) return -1;
if (f[state][k % 2] != 0) return f[state][k % 2];
int hope = k % 2 == 0 ? 1 : -1;
for (int i = 0; i < n; i++) {
if ((state >> i) & 1) continue;
if (tot + i + 1 >= t) return f[state][k % 2] = hope;
if (dfs(state | (1 << i), tot + i + 1, k + 1) == hope) return f[state][k % 2] = hope;
}
return f[state][k % 2] = -hope;
}
bool canIWin(int _n, int _t) {
n = _n; t = _t;
if (t == 0) return true;
f.resize(1 << 20, vector<int>(2, 0));
return dfs(0, 0, 0) == 1;
}
};
时间复杂度：共有 个状态，每个状态转移需要 复杂度，整体复杂度为 空间复杂度：
优化状态表示
进一步发现，若能优化轮数维度，可以有效减少一半的计算量，我们调整状态定义为：定义 为当前状态为 ，「当前先手」能否获胜（ 代表能， 代表不能）。
同时调整递归函数为 ，最终答案通过判断 dfs(0, 0) 是否为 来得知。
注意这里调整的重点在于：将记录「原始回合的先后手发起 和 原始回合的先后手获胜情况」调整为「当前回合发起 和 当前回合获胜情况」。
Java 代码：
class Solution {
int n, t;
int[] f = new int[1 << 20];
// 1 true / -1 false
int dfs(int state, int tot) {
if (f[state] != 0) return f[state];
for (int i = 0; i < n; i++) {
if (((state >> i) & 1) == 1) continue;
if (tot + i + 1 >= t) return f[state] = 1;
if (dfs(state | (1 << i), tot + i + 1) == -1) return f[state] = 1;
}
return f[state] = -1;
}
public boolean canIWin(int _n, int _t) {
n = _n; t = _t;
if (n * (n + 1) / 2 < t) return false;
if (t == 0) return true;
return dfs(0, 0) == 1;
}
}
C++ 代码：
class Solution {
public:
int n, t;
vector<int> f;
int dfs(int state, int tot) {
if (f[state] != 0) return f[state];
for (int i = 0; i < n; i++) {
if ((state >> i) & 1) continue;
if (tot + i + 1 >= t) return f[state] = 1;
if (dfs(state | (1 << i), tot + i + 1) == -1) return f[state] = 1;
}
return f[state] = -1;
}
bool canIWin(int _n, int _t) {
n = _n; t = _t;
if (n * (n + 1) / 2 < t) return false;
if (t == 0) return true;
f.resize(1 << 20, 0);
return dfs(0, 0) == 1;
}
};
Python 代码：
class Solution:
def __init__(self):
self.n = 0
self.t = 0
self.f = [0] * (1 << 20)
def dfs(self, state, tot):
if self.f[state] != 0:
return self.f[state]
for i in range(self.n):
if (state >> i) & 1:
continue
if tot + i + 1 >= self.t:
self.f[state] = 1
return 1
if self.dfs(state | (1 << i), tot + i + 1) == -1:
self.f[state] = 1
return 1
self.f[state] = -1
return -1
def canIWin(self, _n, _t):
self.n = _n
self.t = _t
if self.n * (self.n + 1) // 2 < self.t:
return False
if self.t == 0:
return True
return self.dfs(0, 0) == 1
时间复杂度：共有 个状态，每个状态转移需要 复杂度，整体复杂度为 空间复杂度：
最后
巨划算的 LeetCode 会员优惠通道目前仍可用 ~
使用福利优惠通道 leetcode.cn/premium/?promoChannel=acoier，年度会员 有效期额外增加两个月，季度会员 有效期额外增加两周，更有超大额专属 🧧 和实物 🎁 福利每月发放。
我是宫水三叶，每天都会分享算法知识，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。
