資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學Python實現石頭遊戲中最大得分程式
假設有一排石頭，每塊石頭都有一個關聯數字，這些數字儲存在一個數組`stoneValue`中。在每一輪中，阿馬爾將這排石頭分成兩部分，然後比馬爾計算每一部分的值（該部分中所有石頭的值的總和）。比馬爾丟棄值最大的部分，阿馬爾的得分增加剩餘部分的值。當兩部分的值相同時，比馬爾讓阿馬爾決定丟棄哪一部分。下一輪以剩餘部分開始。當只剩下一塊石頭時，遊戲結束。我們需要找到阿馬爾可以獲得的最大得分。
因此，如果輸入類似於`stoneValue = [7,3,4,5,6,6]`，則輸出為：
第一輪，阿馬爾將這一排石頭分成兩部分：[7,3,4]，[5,6,6]。左邊部分的總和是14，右邊部分的總和是17。比馬爾丟棄右邊部分，阿馬爾的得分現在是14。
第二輪，阿馬爾將這一排石頭分成兩部分：[7]，[3,4]。比馬爾丟棄左邊部分，阿馬爾的得分變為(14 + 7) = 21。
第三輪，阿馬爾只有一次選擇來劃分這一排石頭，即[3]，[4]。比馬爾丟棄右邊部分，阿馬爾的得分現在是(21 + 3) = 24。
為了解決這個問題，我們將遵循以下步驟：
定義一個函式`dfs()`。它將接收起始位置`start`和結束位置`end`。
如果`start >= end`，則
返回0
`max_score := 0`
對於`cut`從`start`到`end`的範圍，執行以下操作：
`sum1 := partial_sum[start, cut]`
`sum2 := partial_sum[cut+1, end]`
如果`sum1 > sum2`，則
`score := sum2 + dfs(cut+1, end)`
否則，如果`sum1 < sum2`，則
`score := sum1 + dfs(start, cut)`
否則，
`score := sum1 + max(dfs(start, cut), dfs(cut+1, end))`
`max_score := max(score, max_score)`
返回`max_score`
定義一個函式`getPartialSum()`。它將接收
對於`i`從0到`n - 1`的範圍，執行以下操作：
`partial_sum[i, i] := stoneValue[i]`
對於`i`從0到`n - 1`的範圍，執行以下操作：
對於`j`從`i+1`到`n - 1`的範圍，執行以下操作：
`partial_sum[i, j] := partial_sum[i, j-1] + stoneValue[j]`
在主方法中，執行以下操作：
`n := stoneValue`的大小
`partial_sum :=`一個大小為n x n的二維陣列，並填充為0
`getPartialSum()`
返回`dfs(0, n-1)`
示例
讓我們看看下面的實現以更好地理解
def solve(stoneValue): def dfs(start, end): if start >= end: return 0 max_score = 0 for cut in range(start, end): sum1 = partial_sum[start][cut] sum2 = partial_sum[cut+1][end] if sum1 > sum2: score = sum2+dfs(cut+1, end) elif sum1 < sum2: score = sum1+dfs(start, cut) else: score = sum1+max(dfs(start, cut), dfs(cut+1, end)) max_score = max(score, max_score) return max_score def getPartialSum(): for i in range(n): partial_sum[i][i] = stoneValue[i] for i in range(n): for j in range(i+1, n): partial_sum[i][j] = partial_sum[i][j-1]+stoneValue[j] n = len(stoneValue) partial_sum = [[0]*n for _ in range(n)] getPartialSum() return dfs(0, n-1) stoneValue = [7,3,4,5,6,6] print(solve(stoneValue))
輸入
[7,3,4,5,6,6]
輸出
0
235 次瀏覽
