题解报告LeetCode#464： Can I Win
思路：
这道题其实还是动态博弈类问题，不过有些不同的地方就是在记忆化的过程中有状态压缩的这个概念的引入。
- 方法一：记忆化回溯
记忆化回溯（也称为递归 + 备忘录），自顶向下。采用记忆化后的时间复杂度为O(2^n)（如果不进行记忆的话，时间复杂度将是O(n!)），可以理解为已经缩成只有一个分支了。
然后为什么要采用记忆化：
因为我们发现，例如 [2, 3] 和 [3, 2] 之后的玩家状态都是一样的，都是可以从除了 2， 3之外的数字进行选择，那么就可以对选择 2 和 3 后第一个玩家能不能赢进行记忆化存储，这里采用state[]数组存储每个数字是否被使用过，选过则记录为1，然后我们将state.toString()使得[2, 3]和[3, 2]它们的结果都是一样的 “0011”，作为key，存储在 HashMap 中，value 是选了 2 和 3。 - 方法二：状态 DP
由于状态不可用数组进行传递【在递归当中会受到改变，不能准确定位当前状态】，所以在这里使用 Int 的位表示状态（1表示用过，0表示未用过），这里采用 DP 状态压缩的方式，思想与回溯类似，只是这里的状态被压缩成一个 bitArray 了。状态压缩，我们可以用二进制第 i 位的 0 或者 1 来表示这个数字的选取与否，这样所有数组的状态就可以用一个数来很方便的表示，题目说了不超过 20 位，所以这里就可以用一个 int 来表示状态 state，通过 state 来判断状态是否一致，故而进行记忆化存取。
代码：
方法一```java class Solution {
public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
if (maxChoosableInteger > desiredTotal) return true;if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false;int[] state = new int[maxChoosableInteger + 1];return backtraceWithMemo(state, desiredTotal, new HashMap<String, Boolean>());
}
private boolean backtraceWithMemo(int[] state, int desiredTotal, HashMap
//状态压缩在这一步体现， //对于[2, 3] 还是 [3, 2]这两种选择，在state中都是体现为 [0,1,1]， //所以这两种状态可以压缩为同一种状态 String key = Arrays.toString(state); if (map.containsKey(key)) { return map.get(key); } for (int i = 1; i < state.length; i++) { if (state[i] != 1) { state[i] = 1; //如果当前选了i已经赢了或者选了i还没赢但是后面对方选择输了 //零和博弈，能让对方输至少就算自己赢 if (desiredTotal - i <= 0 || !backtraceWithMemo(state, desiredTotal - i, map)) { map.put(key, true); state[i] = 0; return true; } } //如果不能赢也要记得回溯 state[i] = 0; } //如果都赢不了，将状态保存后返回 false map.put(key, false); return false;} } ```
方法二```java /**
- @Description:
- 由于状态不可用数组进行传递【在递归当中会受到改变，不能准确定位当前状态】，故在此处用Int的位表示状态（1表示用过,0表示未用过）
- 这里采用DP状态压缩的方式，思想与回溯类似，只是这里的状态被压缩成了一个bitArray了
- 状态压缩，我们可以用二进制的第i位的0或者1来表示i这个数字的选取与否，这样所有数字的选取状态就可以用一个数来很方便的表示，
题目说了不超过20位，所以这里就可以用一个int来表示状态state，通过state来判断状态是否一致，进而进行记忆化的存取 */ public class Solution {
public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
if (maxChoosableInteger >= desiredTotal) return true; if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false; /** * dp表示"每个"取数(A和B共同作用的结果)状态下的输赢 * 例如只有1,2两个数选择，那么 (1 << 2) - 1 = 4 - 1 = 3种状态表示： * 01,10,11分别表示：A和B已经选了1，已经选了2，已经选了1、2状态下，A的输赢情况 * 并且可见这个表示所有状态的dp数组的每个状态元素的长度为maxChoosableInteger位的二进制数 */ Boolean[] dp = new Boolean[(1 << maxChoosableInteger) - 1]; return dfs(maxChoosableInteger, desiredTotal, 0, dp);}
/**
- @param maxChoosableInteger 选择的数的范围[1,2,…maxChoosableInteger]
- @param desiredTotal 目标和
- @param state 当前状态的十进制表示（记录着可能不止一个数被选择的状态）
- @param dp 记录所有状态
- @return
*/
private boolean dfs(int maxChoosableInteger, int desiredTotal, int state, Boolean[] dp) {
if (dp[state] != null)
/**return dp[state];- 例如maxChoosableInteger=2，选择的数只有1,2两个，二进制只要两位就可以表示他们的选择状态
- 最大位为2（第2位），也就是1 << (2 - 1)的结果，所以最大的位可以表示为 1 << (maxChoosableInteger - 1)
- 最小的位可以表示为 1 << (1 - 1)，也就是1（第1位）
- 这里i表示括号的范围
/
for (int i = 1; i <= maxChoosableInteger; i++){
//当前待抉择的位，这里的tmp十进制只有一位为1，用来判断其为1的位，对于state是否也是在该位上为1
//用以表示该位（数字）是否被使用过
/*
- (&运算规则，都1才为1)
- 例如,i=3, tmp = 4, state = 3;
- 100
- &011
- =0 表示该位没有被使用过，也就是第三位没有被使用过，即数字3 (i)没有被使用过
/
int tmp = (1 << (i - 1));
if ((tmp & state) == 0){ //该位没有被使用过
//如果当前选了i已经赢了或者选了i还没赢但是后面对方选择输了,tmp|state表示进行状态的更新
/*
- 例如
- 100
- |011
- =111 */ //注意这里并没有像回溯一样进行状态的(赋值化的)更新、回溯 //其实这里是隐含了回溯的，我们通过参数传递更新后的state //但是我们在这个调用者这里的state还是没有进行更新的，所以 //就相当于回溯了状态。 if (desiredTotal - i <= 0 || !dfs(maxChoosableInteger, desiredTotal - i, tmp|state, dp)) { dp[state] = true; return true; } } } //如果都赢不了 dp[state] = false; return false; } } ```
若有收获，就点个赞吧
0 人点赞
