464. 我能赢吗

本文主要是介绍464. 我能赢吗，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：

464. 我能赢吗

https://leetcode.cn/problems/can-i-win/description/

完成情况：

解题思路：

这段代码是一个使用深度优先搜索（DFS）和记忆化搜索（Memoization）的算法，用于解决一个游戏问题。下面是代码的解释：

1. canIWin 方法：这个方法用于判断玩家是否能赢得游戏。首先，它会检查是否所有可选整数之和小于期望的总数，如果是，则返回 false，否则调用 dfs 方法。

2. dfs 方法：这个方法是深度优先搜索的核心。它会递归地尝试所有可能的选择，记录已经使用过的数字，并在适当的时候进行回溯。具体步骤如下：

   • 如果当前的选择已经被记录在 memo 中，则直接返回 memo 中对应的结果。
   • 否则，遍历所有可选整数，检查是否该整数已经被使用过。
   • 如果该整数未被使用，判断选择该整数后是否能达到或超过期望的总数，如果是，则返回 true。
   • 否则，递归调用 dfs 方法，更新已使用数字的状态，并继续搜索下一个选择。
   • 最后，将当前选择的结果存入 memo 中，并返回该结果。

这段代码的目的是找出在给定规则下，玩家是否能赢得游戏。通过记忆化搜索，避免重复计算，提高了算法的效率。

参考代码：

_464我能赢吗_记忆化dp

package leetcode板块;import java.util.HashMap;
import java.util.Map;public class _464我能赢吗_记忆化dp {Map<Integer,Boolean> memoery = new HashMap<Integer,Boolean>();/**** @param maxChoosableInteger* @param desiredTotal* @return*/public boolean canIWin(int maxChoosableInteger, int desiredTotal) {//  两名玩家轮流 -> 选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过  100 的玩家，即为胜者。//  如果我们将游戏规则改为 【“玩家 不能 重复使用整数”】 呢？/*两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家能稳赢则返回 true ，否则返回 false 。假设两位玩家游戏时都表现 最佳 。允许选择使用重复的数   -->  先手是否一定能赢？*/if ((1 + maxChoosableInteger) * (maxChoosableInteger) / 2 < desiredTotal){  //如果这些数的累计和的一半不超过目标值，那么永远不可能满足需求return false;}return dfs_canIWin(maxChoosableInteger,0,desiredTotal,0);}/*** 见名知意* @param maxChoosableInteger* @param usedNumbers* @param desiredTotal* @param currentTotals* @return*/private boolean dfs_canIWin(int maxChoosableInteger, int usedNumbers, int desiredTotal, int currentTotals) {if (!memoery.containsKey(usedNumbers)){boolean result = false;for (int i = 0;i<maxChoosableInteger;i++){  //在这些数中每次都选取最大的数？if (((usedNumbers >> i) & 1) == 0){  //从低位到高位开始取值if (i + 1 + currentTotals >= desiredTotal){result = true;break;}if (!dfs_canIWin(maxChoosableInteger, usedNumbers | (1 << i), desiredTotal, currentTotals+i+1)){result = true;break;}}}memoery.put(usedNumbers,result);}return memoery.get(usedNumbers);}
}

错误经验吸取

这篇关于464. 我能赢吗的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---