資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++石頭遊戲
假設有兩名玩家Alex和Lee，他們玩一個石頭堆的遊戲。有偶數堆石頭排成一排，每堆石頭數量為piles[i]。遊戲的目標是擁有最多的石頭。當石頭總數為奇數時，沒有平局。Alex先開始，玩家輪流從一排石頭的開頭或結尾取走整堆石頭。直到沒有石頭堆剩下，擁有最多石頭的人獲勝。假設Alex和Lee都採取最佳策略，檢查Alex是否會贏。例如，如果輸入是[5,3,4,5]，則結果為true，因為Alex先開始，他只能取走第一個5或最後一個5。如果他取走第一個5，則排變成[3, 4, 5]。如果Lee取走3，則排變成[4, 5]，Alex取走5獲勝，得分為10。如果Lee取走最後一個5，則排變成[3, 4]，Alex取走4獲勝，得分為9。這表明取走第一個5對Alex來說是一個獲勝的策略，答案為true。
為了解決這個問題，我們將遵循以下步驟：
n := piles陣列的大小
建立一個大小為n x n的矩陣dp，建立一個大小為n + 1的陣列pre
對於i從0到n – 1
pre[i + 1] := pre[i] + piles[i]
對於l從2到n −
對於i := 0, j := l – 1, j < n, i和j遞增1
dp[i, j] := piles[j] + pre[j] – pre[i] – dp[i, j – 1] 和 piles[i] + pre[i + 2] – pre[j] + dp[i + 1, j] 的最大值
當dp[0, n – 1] > dp[0, n – 1] – pre[n]時返回true
讓我們來看下面的實現以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool stoneGame(vector<int>& piles) {
int n = piles.size();
vector < vector <int> > dp(n,vector <int>(n));
vector <int> pre(n + 1);
for(int i = 0; i < n; i++){
pre[i + 1] = pre[i] + piles[i];
}
for(int l = 2; l <= n; l++){
for(int i = 0, j = l - 1; j < n; i++, j++){
dp[i][j] = max(piles[j] + pre[j] - pre[i] - dp[i][j - 1], piles[i] + pre[i + 2] - pre[j] + dp[i + 1][j]);
}
}
return dp[0][n - 1] > dp[0][n - 1] - pre[n];
}
};
main(){
vector<int> v = {5,3,4,5};
Solution ob;
cout << (ob.stoneGame(v));
}輸入
[5,3,4,5]
輸出
1
更新於：2020年4月30日
466 次瀏覽
廣告