Python中寻找石头游戏中的最高分数的程序

假设有几个石头放置在一排中，每个石头都有一个与之关联的数字，在数组stoneValue中给出。在每一轮中，Amal把该行分成两部分，然后Bimal计算每部分的值，即该部分所有石头的值的总和。Bimal丢弃具有最大值的部分，Amal的分数增加剩下部分的值。当两部分的值相同时，Bimal让Amal决定将哪个部分丢弃。下一轮从剩下的部分开始。游戏在只剩下一块石头时结束。我们需要找到Amal可以获得的最高分数。

因此，如果输入是stoneValue =[7,3,4,5,6,6]，则输出将是

在第1轮中，Amal将行分成[7,3,4]，[5,6,6]。左边的行的总和为14，右边的行的总和为17。Bimal丢弃了右行，Amal的分数现在是14。
在第二轮中，Amal将行分成[7]，[3,4]。所以Bimal抛弃了左边的行，Amal的分数变成了（14 + 7）= 21。
在第3轮中，Amal只有一种选择来分割行，即[3]，[4]。Bimal丢弃右边的行，Amal的分数现在为（21 + 3）= 24。

为了解决这个问题，我们将按以下步骤执行−

定义一个函数dfs()。这将获取start，end
如果start≥end，则
- 返回0
max_score：=0
对于在范围内的切割，do
- sum1：=partial_sum[start，cut]
- sum2：=partial_sum[cut + 1，end]
- 如果sum1>sum2，则
  - 得分：=sum2 + dfs（cut + 1，end）
- 否则，当sum1
  - 得分：=sum1 + dfs（start，cut）
- 否则，
  - 得分：=sum1 +dfs(start,cut)和dfs(cut + 1, end)的最大值
- max_score：=得分和max_score的最大值
返回max_score
定义一个函数getPartialSum()。这将获取
在0到n-1范围内，do
- partial_sum[i，i]：=stoneValue[i]
在0到n-1范围内，do
- for j in range i + 1 to n – 1, do
  - partial_sum[i，j]：=partial_sum[i，j-1]+stoneValue[j]

从主方法开始，按以下步骤执行

n：=stoneValue的大小
partial_sum：=大小为n x n的方形数组，填充为0
getPartialSum()
返回dfs（0，n-1）

示例

让我们看一下以下实现，以获得更好的理解

“`python def solve(stoneValue):
def dfs(start, end):
if start >= end:
return 0
max_score = 0

<pre><code> 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))
</code></pre>

<pre><code class="line-numbers">## 输入
“`python [7,3,4,5,6,6]“`

## 输出
“`python 0