【 알고리즘 문제 】 바둑 이론: leetcode 486 수조 취수

알현하다
【제목】:
정수조를 정하고 선수1은 수조의 머리나 꼬리에서 하나의 수를 선택하며 선수2는 나머지 부분의 머리나 꼬리에서 하나의 수를 선택하여 이 수조의 수가 다 뽑힐 때까지 순환한다.선수 하나, 둘 다 똑똑하다.선수가 1을 취한 수의 합치가 선수보다 큰지 판단하다.
【사고방식】:
pp[i][j]는 원수 그룹 중 i에서 j까지의 이 다수 중 게임 규칙에 따라 한 유저가 얻을 수 있는 최대 점수를 나타낸다.
dp[i][j]=max(sum[i][j]−dp[i+1][j],sum[i][j]−dp[i][j−1])
주: dp[i][j]=max(sum[i+1][j]-3-dp[i+1][j]+nums[i],sum[i][j-1]-3dp[i][j-1]+nums[j])

#include 
#include 
#include 
#include 
#include 

using namespace std;

bool PredictTheWinner(vector<int>& nums)
{
    int n = nums.size();
    vector<vector<int>> dp(n, vector<int>(n));
    vector<int> sum(n);

    for (int i = 0; i < n; i++)
        dp[i][i] = nums[i];

    sum[0] = nums[0];

    for (int i = 0; i < n - 1; i++)
        sum[i + 1] = sum[i] + nums[i + 1];//     

    //  
    for (int i = 1; i < n; i++)
        for (int j = 0; i + j < n; j++)
            dp[j][i + j] = max(sum[i + j] - sum[j] + nums[j] - dp[j + 1][i + j], sum[i + j] - sum[j] + nums[j] - dp[j][i + j - 1]);

    return 2 * dp[0][n - 1] >= sum[n - 1];
}

int main()
{
    vector<int>  vec{1,2,3,4,5,6};
    cout<return 0;
}