資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++石頭遊戲II
假設有兩個人Alice和Bob，他們正在用一堆石頭玩遊戲。排成一排的若干堆石頭，每堆石頭數量為正整數，儲存在陣列piles[i]中。遊戲目標是獲得最多石頭。Alice先開始，Bob後開始。初始M = 1。每輪，玩家可以選擇取走剩餘石頭中前X堆石頭，其中1 <= X <= 2M。然後，設定M = max(M, X)。當沒有石頭剩餘時遊戲結束。例如，piles = [2,7,9,4,4]，則輸出為10。因為如果Alice一開始取一堆，Bob取兩堆，Alice再取兩堆，Alice可以得到2 + 4 + 4 = 10堆石頭。如果Alice一開始取兩堆，Bob可以取剩下的三堆，Alice得到2 + 7 = 9堆石頭。所以返回10，因為它更大。
為了解決這個問題，我們將遵循以下步驟：
- 建立一個名為solve的遞迴函式，它將接收陣列、i、m和一個名為dp的矩陣。
- 如果i >= arr的大小，則返回0
- 如果dp[i, m]不等於-1，則返回dp[i, m]
- 如果i – 1 + 2m >= 陣列大小，則返回arr[i]
- op := inf
- 對於x從1到2m的範圍
- op := op, solve(arr, i + x, max(x, m), dp) 的最小值
- dp[i, m] := arr[i] – op
- 返回dp[i, m]
- 實際方法如下：
- n := piles陣列的大小，建立一個大小為n的陣列arr
- arr[n - 1] := piles[n – 1]
- 對於i := n – 2到0遞減
- arr[i] := arr[i + 1] + piles[i]
- 建立一個大小為(n + 1) x (n + 1)的矩陣，並將其填充為-1
- 返回solve(arr, 0, 1, dp)
讓我們看看下面的實現來更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
void printVector(vector <int> v){
for(int i =0;i<v.size();i++)cout << v[i] << " ";
cout << endl;
}
int stoneGameII(vector<int>& piles) {
int n = piles.size();
vector <int> arr(n);
arr[n-1] = piles[n-1];
for(int i = n-2;i>=0;i--)arr[i] = arr[i+1] + piles[i];
vector < vector <int> > dp(n+1,vector <int> (n+1,-1));
return solve(arr,0,1,dp);
}
int solve(vector <int> arr, int i, int m, vector < vector <int> > &dp){
if(i >=arr.size())return 0;
if(dp[i][m]!=-1)return dp[i][m];
if(i-1+2*m >=arr.size())return arr[i];
int opponentCanTake = INT_MAX;
for(int x =1;x<=2*m;x++){
opponentCanTake = min(opponentCanTake,solve(arr,i+x,max(x,m),dp));
}
dp[i][m] = arr[i] - opponentCanTake;
return dp[i][m];
}
};
main(){
vector<int> v = {2,7,9,4,4};
Solution ob;
cout <<(ob.stoneGameII(v));
}輸入
[2,7,9,4,4]
輸出
10
更新於：2020年4月30日
367 次瀏覽
廣告