c - 在这个 DP 问题中左移的目的是什么？

Question

我最近在网上找到了这个问题的解决方案（来自 leetcode.com）：

在“100 游戏”中，两名玩家轮流将 1..10 中的任何整数加到运行总数中。最先使总分达到或超过 100 的玩家获胜。如果我们改变游戏规则让玩家不能重复使用整数会怎样？例如，两名玩家可能会轮流从 1..15 的公共号码池中抽奖，直到总数 >= 100。

给定一个 integermaxChoosableInteger和另一个 integer desiredTotal，确定第一个移动的玩家是否可以强制获胜，假设两个玩家都发挥最佳。您始终可以假设maxChoosableInteger不会大于 20 并且desiredTotal不会大于 300。

int canWin(int *dp, int v, int m, int total) {
    int i, hewins;

    if (dp[v] != -1) return dp[v];      // already resolved

    for (i = m; i >= 1; i --) {
        if (v & (1 << (i - 1))) continue;
        v |= (1 << (i - 1));
        if (i >= total) {
            dp[v] = 1;          // resolve to win
            return 1;
        }
        hewins = canWin(dp, v, m, total - i);
        if (!hewins) return 1;
        v &= ~(1 << (i - 1));   // not able to resolve, try with different number
    }
    dp[v] = 0;      // resolve to loose
    return 0;
}
bool canIWin(int maxChoosableInteger, int desiredTotal) {
    int w, dp[1 << 20];

    // none can win
    if (maxChoosableInteger * (maxChoosableInteger + 1) / 2 < desiredTotal) return false;

    //dp = calloc((1 << (maxChoosableInteger)), sizeof(int));
    //assert(dp);
    memset(dp, -1, (1 << (maxChoosableInteger)) * sizeof(int));

    w = canWin(dp, 0, maxChoosableInteger, desiredTotal);

    //free(dp);

    return w;
}

在上面的代码中，有 3 个主要的实例使用了左移。

    memset(dp, -1, (1 << (maxChoosableInteger)) * sizeof(int));

和

dp[1 << 20]

以及所有类似的实例：

        if (v & (1 << (i - 1))) continue;

问题的解决方案是递归的，这个问题是递归解决的，但首先我不确定为什么需要这么大的数组来存储所有递归调用。每个输入最多应该有 20 次递归调用（因为canIWin(maxinteger, total) = canIWin(maxInteger - 1), total) OR canIWin((maxInteger - 2), total) OR...... canIWin(1, total)（由于逻辑原因，它实际上不能达到 1，但这只是让想法得以理解）

任何解释为什么使用这种左移将不胜感激。

标签： c