Dự đoán người chiến thắng trong C++

Giới thiệu

Hai người chơi lần lượt lấy số từ đầu hoặc cuối mảng điểm số. Mỗi số chỉ được lấy một lần. Người có tổng điểm cao hơn thắng. Dự đoán xem người chơi 1 có thể thắng không (giả sử cả hai chơi tối ưu).

Quy hoạch động (Dynamic Programming)

Sử dụng DP khoảng (Interval DP). Gọi dp[i][j] là hiệu số điểm tối đa mà người chơi hiện tại có thể đạt được so với đối thủ khi còn lại đoạn [i..j].

Công thức:

dp[i][j] = max(arr[i] - dp[i+1][j], arr[j] - dp[i][j-1])

Người 1 thắng nếu dp[0][n-1] >= 0.

Cài đặt C++ (Đơn giản hóa)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(n));
        for (int i = 0; i < n; i++) dp[i][i] = nums[i];
        for (int len = 2; len <= n; len++) {
            for (int i = 0; i + len - 1 < n; i++) {
                int j = i + len - 1;
                dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1]);
            }
        }
        return dp[0][n-1] >= 0;
    }
};

int main() {
    Solution ob;
    vector<int> v = {1, 5, 233, 7};
    cout << ob.PredictTheWinner(v); // Output: 1 (true)
    return 0;
}

Giải thích ví dụ

Mảng: [1, 5, 233, 7]

• Người 1 lấy 1 (đầu). Còn [5, 233, 7].
• Người 2 phải lấy 5 hoặc 7. Nếu lấy 5 → còn [233, 7], người 1 lấy 233. Tổng P1 = 234, P2 = 12. Nếu người 2 lấy 7 → còn [5, 233], người 1 lấy 233. Tổng P1 = 234, P2 = 12.
• Người 1 luôn thắng.

Độ phức tạp

• Thời gian: O(n²).
• Không gian: O(n²) (có thể tối ưu thành O(n)).