464.我能赢吗
464.我能赢吗
题解
题目：博弈，给定一个maxChoosableInteger和desiredTotal，两个人每次取1~maxChoosableInteger中的数字（不放回），取出的数字累加和超过desiredTotal游戏结束，两个人每次选择都是最优解，问先手的人赢还是后手的人赢
思路：
1.由于maxChoosableInteger 数据量较小，可以用状态压缩 2.因为每次都是最优解，所以要暴力枚举，遍历可以选的元素 3.设当前数字累加为sum，当前想选的新数字为x 4.如果sum+x>=desiredTotal,那么返回true 5.如果!dfs(cur|state, sum+x+1)，那么返回true，即当前选了x后，另一个人一定输 6.否则遍历完还没有返回true的话，那么该状态就是false了 7.存在多个子问题，用记忆化剪枝 8.还有两个小剪枝看代码
代码
func canIWin(maxChoosableInteger int, desiredTotal int) bool { mp := make(map[int]bool) var dfs func(state int, sum int) bool dfs = func(state int, sum int) bool { if _, ok := mp[state]; ok { return mp[state] } for x := 0; x < maxChoosableInteger; x++ { cur := 1 << x if cur&state == cur { continue } if sum+x+1 >= desiredTotal { mp[state] = true return true } if !dfs(cur|state, sum+x+1) { mp[state] = true return true } } mp[state] = false return false } if maxChoosableInteger >= desiredTotal { return true } if maxChoosableInteger*(maxChoosableInteger+1)/2 < desiredTotal { return false } return dfs(0, 0) }
func canIWin(maxChoosableInteger int, desiredTotal int) bool { mp := make(map[int]bool) var dfs func(choose int, sum int) bool dfs = func(state int, sum int) bool { if _, ok := mp[state]; ok { return mp[state] } for x := 0; x < maxChoosableInteger; x++ { cur := state >> x if cur&1 == 1 { continue } if sum+x+1 >= desiredTotal { mp[state] = true return true } if !dfs((1<<x)|state, sum+x+1) { mp[state] = true return true } } mp[state] = false return false } if maxChoosableInteger >= desiredTotal { return true } if maxChoosableInteger*(maxChoosableInteger+1)/2 < desiredTotal { return false } return dfs(0, 0) }
