c# - 改进 C# 中的递归方法

Question

这是我的代码:

    static int cardGameValue(List<int> D, int myScore, int opponentScore)
    {
        if (D.Count == 0) return myScore;
        else if (D.Count == 1)
        {
            opponentScore += D[0];
            return myScore;
        }
        else
        {
            if (D[0] <= D[D.Count - 1])
            {
                opponentScore += D[D.Count - 1];
                D.RemoveAt(D.Count - 1);
            }
            else
            {
                opponentScore += D[0];
                D.RemoveAt(0);
            }

            int left = cardGameValue(new List<int>(D.GetRange(1, D.Count - 1)), myScore + D[0], opponentScore);

            int right = cardGameValue(new List<int>(D.GetRange(0, D.Count - 1)), myScore + D[D.Count - 1], opponentScore);

            if (left >= right)
            {
                return left;
            }
            else
            {
                return right;
            }
        }
    }
}

我的代码采用一组纸牌，代表您在与确定性对手对战时的最​​大可能得分。在你的对手每玩一次之后，你有 2 个选择，直到所有牌都被选中。有没有办法以某种方式存储我的迭代结果，以便改进我的算法？所以递归不会做不必要的迭代？因为在 40 或 50 张卡片之后它变得非常慢。

Answer 1

您只能访问列表 D 中的第一个或最后一个元素。您可以传递完整的卡片列表(或者更好:作为 int 数组)以及第一个和最后一个位置的索引，而不是传递确切的列表。

计算完成后计算对手的分数会快很多:myScore和opponentScore相加就是牌面值的总和，所以你可以做这在 O(n) 时间内。这样，您可以消除所有更新 opponentScore 的代码。

您也不需要传递 myScore。如果您让 cardGameValue 返回仅从剩余卡片中获得的最佳分数。

最后，如果您使用第一个和最后一个索引，则可以将分数存储在二维数组中，由 first 和 last 索引。如果所有的牌都是正值，那么如果至少还剩下两张牌，那么得分一定是正数。

因此在调用开始时，您检查缓存的分数是否为正。如果是，您可以立即返回。如果没有，就得自己计算，然后存入缓存数组。

这就是你最终得到的:

static int cardGameValue(int[] D, int first, int last) {
    scores = new int[last + 1, last + 1];
    return cardGameValue(D, first, last, scores);
}

static int cardGameValue(int[] D, int first, int last, int[,] scores) {
    // If we have at most 1 card, our score is 0:
    if (first >= last)
        return 0;

    // Otherwise, get the score from the cache array. 
    // If it is positive, return the value.
    int score = scores[first, last];
    if (score > 0)
        return score;

    // Keep the original first and last 
    // for filling in the computed value later.
    int firstOriginal = first;
    int lastOriginal = last;

    // Let the opponent pick a card:
    if (D[first] <= D[last])
        last--;
    else
        first++;

    // Choose our best card:
    int left = D[first] + cardGameValue(D, first + 1, last, scores);
    int right = D[last] + cardGameValue(D, first, last - 1, scores);
    score = Math.Max(left, right);

    // and enter the score into the cache array:
    scores[firstOriginal, lastOriginal] = score;

    // Finally, return the computed score.
    return score;
}

即使是 300 张卡片，它在我的机器上的运行时间也不到 1 毫秒。