解题思路

这是一个博弈论问题，使用动态规划求解。关键点：

  1. 状态定义：

    • a[i][j] 表示在区间 [i, j] 内先手能获得的最大分数
    • b[i][j] 表示在区间 [i, j] 内后手能获得的最大分数

  2. 状态转移：

    • 先手可以选择最左或最右的牌：
      • 选左边：A[i] + b[i+1][j]
      • 选右边：A[j] + b[i][j-1]
    • 后手会选择让先手获得最小值：
      • min(a[i+1][j], a[i][j-1])

代码

class Cards {
public:
    int cardGame(vector<int> A, int n) {
        vector<vector<int>> a(n + 1, vector<int>(n, 0));
        vector<vector<int>> b(n + 1, vector<int>(n, 0));
        
        // 初始化单张牌的情况
        a[0][0] = A[0];
        a[n - 1][n - 1] = A[n - 1];
        
        // 区间动态规划
        for(int j = 1; j < n; j++) {
            for(int i = j; i >= 0; i--) {
                a[i][j] = max(A[i] + b[i + 1][j], A[j] + b[i][j - 1]);
                b[i][j] = min(a[i + 1][j], a[i][j - 1]);
            }
        }
        
        return max(a[0][n - 1], b[0][n - 1]);
    }
};

import java.util.*;

public class Cards {
    public int cardGame(int[] A, int n) {
        int[][] a = new int[n + 1][n];
        int[][] b = new int[n + 1][n];
        
        // 初始化单张牌的情况
        a[0][0] = A[0];
        a[n - 1][n - 1] = A[n - 1];
        
        // 区间动态规划
        for(int j = 1; j < n; j++) {
            for(int i = j; i >= 0; i--) {
                a[i][j] = Math.max(A[i] + b[i + 1][j], A[j] + b[i][j - 1]);
                b[i][j] = Math.min(a[i + 1][j], a[i][j - 1]);
            }
        }
        
        return Math.max(a[0][n - 1], b[0][n - 1]);
    }
}

# -*- coding: utf-8 -*-

class Cards:
    def cardGame(self, A, n):
        # 特判
        if n == 0:
            return 0
        if n == 1:
            return A[0]
        
        # 初始化dp数组
        a = [[0] * n for _ in range(n + 1)]
        b = [[0] * n for _ in range(n + 1)]
        
        # 初始化单张牌的情况
        a[0][0] = A[0]
        a[n - 1][n - 1] = A[n - 1]
        
        # 区间动态规划
        for j in range(1, n):
            for i in range(j, -1, -1):
                a[i][j] = max(A[i] + b[i + 1][j], A[j] + b[i][j - 1])
                b[i][j] = min(a[i + 1][j], a[i][j - 1])
        
        return max(a[0][n - 1], b[0][n - 1])

算法及复杂度

  • 算法：区间动态规划
  • 时间复杂度：，需要填充两个 的 dp 数组
  • 空间复杂度：，需要两个 的 dp 数组