C语言 | Leetcode C语言题解之第464题我能赢吗

题目：

题解：

typedef struct HashItem {int key;bool val;UT_hash_handle hh;
} HashItem;bool dfs(int maxChoosableInteger, int usedNumbers, int desiredTotal, int currentTotal, HashItem **memo) {HashItem *pEntry = NULL;HASH_FIND_INT(*memo, &usedNumbers, pEntry);if (NULL == pEntry) {bool 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, memo)) {res = true;break;}}}pEntry = (HashItem *)malloc(sizeof(HashItem));pEntry->key = usedNumbers;pEntry->val = res;HASH_ADD_INT(*memo, key, pEntry);}return pEntry->val;
}bool canIWin(int maxChoosableInteger, int desiredTotal) {HashItem *memo = NULL;if ((1 + maxChoosableInteger) * (maxChoosableInteger) / 2 < desiredTotal) {return false;}return dfs(maxChoosableInteger, 0, desiredTotal, 0, &memo);
}