Java | Leetcode Java题解之第464题我能赢吗
题目:
题解:
class Solution {
Map<Integer, Boolean> memo = new HashMap<Integer, Boolean>();
public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
if ((1 + maxChoosableInteger) * (maxChoosableInteger) / 2 < desiredTotal) {
return false;
}
return dfs(maxChoosableInteger, 0, desiredTotal, 0);
}
public boolean dfs(int maxChoosableInteger, int usedNumbers, int desiredTotal, int currentTotal) {
if (!memo.containsKey(usedNumbers)) {
boolean res = false;
for (int i = 0; i < maxChoosableInteger; i++) {
if (((usedNumbers >> i) & 1) == 0) {
if (i + 1 + currentTotal >= desiredTotal) {
res = true;
break;
}
if (!dfs(maxChoosableInteger, usedNumbers | (1 << i), desiredTotal, currentTotal + i + 1)) {
res = true;
break;
}
}
}
memo.put(usedNumbers, res);
}
return memo.get(usedNumbers);
}
}
原文地址:https://blog.csdn.net/m0_57195758/article/details/142773192
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!