leetcode 464. Can I Win | 464. 我能赢吗（博弈论，动态规划）

题目

https://leetcode.com/problems/can-i-win/

题解

来看下 Related Topics：

对于一个博弈论问题，我给这题点踩。对于一个 dp 问题，我给这题点赞。

一开始我以为这是一个数学问题，于是尝试找规律，没有进展。后来看了答案才知道，这是一个暴力的记忆化 DFS，也就是 dp。

思路

参考讨论区：464. 我能赢吗，带备忘录的递归，讲的很清晰。

class Solution {public boolean canIWin(int max, int target) {if ((1 + max) * max / 2 < target) return false;Map<Integer, Boolean> dp = new HashMap<>(); //<state,canWin>return tryWin(max, 0, target, dp);}public boolean tryWin(int max, int state, int target, Map<Integer, Boolean> dp) {if (dp.containsKey(state)) return dp.get(state);for (int i = 1; i <= max; i++) {if (((state >> i) & 1) == 0) { // 数字i未使用int newState = state | (1 << i);if (i >= target || !tryWin(max, newState, target - i, dp)) { // 我此轮能赢，或对方以后不能赢dp.put(state, true);return true;}}}dp.put(state, false);return false;} }

总结

以上是生活随笔为你收集整理的leetcode 464. Can I Win | 464. 我能赢吗（博弈论，动态规划）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。