algorithm - 最大利益 - メモ化、DP、最適化

Question

私はアルゴリズムゲームで問題を練習していました.次の問題を試しましたが、それを行う効率的な方法を見つけることができませんでした::

では、私を助けていただけませんか。ここに問題があります。

これは正確なリンクです:: http://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=srm228

Answer 1

動的計画法を使用してそれを解決できます。状態は次のように表すことができます。

set of available coins,
whos turn it is

州ごとに、その人が勝つことができる最大金額を計算する必要があります。

ヒント：このゲームのルールではset of available coins、間隔として説明できます。

@編集

for(int interval_size = 1; interval_size <= n; interval_size++) {
    for(int interval_start = 0; interval_start + interval_size <= n; interval_start++) {
         // result[interval_start][interval_start + interval_size] depends only on
         // -> result[interval_start][interval_start + interval_size - 1]
         // -> result[interval_start + 1][interval_start + interval_size]
    }
}

Answer 2

しましょうdp[i, j] = maximum profit alice can make for the coints i, ... j。

我々は持っています：

dp[i, i] = input[i] for all 1 <= i <= N
dp[i, i + 1] = max(input[i], input[i + 1])
dp[i, j] = max(// take first coin, opponent will minimize your next move
               input[i] + min(dp[i + 2, j], dp[i + 1, j - 1]),
               // take last coin, opponent will still minimize your next move
               input[j] + min(dp[i, j - 2], dp[i - 1, j - 1]))

Answer 3

この問題を自分で解決したいと思っていると思いますので、ヒントを与えます: この問題には最適な部分構造があります。

コインの両方のソリューションがあると想像してくださいN-1(左端と右端のソリューションはありません)。Nそれでは、コインの解を計算するのは簡単でしょうか?

このプロパティを利用するには、関連する 2 つの手法 (動的プログラミングと、メモ化と呼ばれるそのサブタイプ)を使用できます。Lアイデアは、コインが左からR欠け、コインが右から欠けている各サブ問題の解決策を格納することです (NxN配列を使用します)。サブ問題を解決する前に、配列をチェックして、既に解決済みかどうかを確認してください。N^2/2解決策にたどり着くには、ほとんどの部分問題を解決する必要があります。

メモ化されたソリューションの擬似コードは次のとおりです。

// solved[L][R] array contains the highest value a player could get
// on a subproblem where L coins are missing from the left
// and R are missing from the right of the original sequence on his move
int solved[N][N] // initialize each element to -1.
int coins[N]     // initialize with coin values 

int solve(int L, int R) {
    if (L+R == N) return 0; // No coins remain
    if (solved[L][R] >= 0) return solved[L][R];
    int remaining = sum(coins from L to R)
    int takeLeft = remaining - solve(L+1, R);
    int takeRight = remaining - solve(L, R+1);
    int result = max(takeLeft, takeRight);
    solved[L][R] = result;
    return result;
}

main() {
    int alice = solve(0, 0);
    int bob = sum(coins) - alice;
}

2005 年か 2006 年の初めに TopCoder がこの問題を実行していたことを覚えていますが、問題のアーカイブを検索するのに十分な詳細を覚えていません。

Answer 4

//@ IVlad ::Implement your code ,its giving incorrect answer.Had I implemented it properly??
int coins[1000];
int dp[1000][1000];
int main()
 {
int T,N;//N=How many coins are there
cin>>T; //No of Test Cases.
while(T--)
{
    cin>>N;
    for(int i=1;i<=N;++i)
    {
        cin>>coins[i];
    }
    for(int i=1;i<=N;++i)
    {
        dp[i][i]=coins[i];
    }
    for(int i=1;i<=N;++i)
    {
        if(i+1<=N)
        dp[i][i + 1] = max(coins[i], coins[i + 1]);
    }
    for(int i=1;i<=N;++i)
    {
        for(int j=1;j<=N;++j)
        {
            if((i+2)<=N && (i+1)<=N && (j-2)>=1 && (i-1)>=1 && (j-1)>=1)
            dp[i][j]=max( (coins[i] + min(dp[i + 2] [j], dp[i + 1][ j - 1])),coins[j] + min(dp[i] [j - 2], dp[i - 1] [j - 1]));
        }
    }
    cout<<dp[1][N]<<endl;//Answer
}

return 0;

}