当前位置: 面试刷题>> 取数游戏 (经典算法题500道)


题目描述补充

取数游戏是一种有趣的策略游戏,玩家从一排给定的非负整数数组中,按照特定的规则选取数字。游戏规则如下:

  1. 玩家每次可以从数组的两端(即数组的第一个元素或最后一个元素)选择一个数字,并将其从数组中移除。
  2. 被移除的数字将会加到玩家的得分中。
  3. 游戏继续进行,直到数组中的所有数字都被移除。
  4. 玩家的目标是最大化自己的最终得分。

现在,你需要编写一个程序,实现一个函数来找出并返回玩家按照最优策略进行游戏时能获得的最大得分。

示例

给定数组 [2, 7, 9, 3, 1],最优的选择顺序可能是:

  1. 选择 7(数组变为 [2, 9, 3, 1]),得分 7
  2. 选择 9(数组变为 [2, 3, 1]),得分 9
  3. 选择 3(数组变为 [2, 1]),得分 3
  4. 选择 2(数组变为 [1]),得分 2
  5. 选择 1(数组为空),得分 1

因此,最大得分为 7 + 9 + 3 + 2 + 1 = 22。

PHP 示例代码

function getMaxScore($nums) {
    $n = count($nums);
    $dp = array_fill(0, $n, array_fill(0, $n, 0));
    
    // 初始化对角线上的值为数组元素本身
    for ($i = 0; $i < $n; $i++) {
        $dp[$i][$i] = $nums[$i];
    }
    
    // 动态规划填表
    for ($len = 2; $len <= $n; $len++) {
        for ($i = 0; $i <= $n - $len; $i++) {
            $j = $i + $len - 1;
            $dp[$i][$j] = max($nums[$i] + $dp[$i + 1][$j], $nums[$j] + $dp[$i][$j - 1]);
        }
    }
    
    return $dp[0][$n - 1];
}

// 测试
$nums = [2, 7, 9, 3, 1];
echo getMaxScore($nums); // 输出: 22

Python 示例代码

def getMaxScore(nums):
    n = len(nums)
    dp = [[0] * n for _ in range(n)]
    
    # 初始化对角线上的值为数组元素本身
    for i in range(n):
        dp[i][i] = nums[i]
    
    # 动态规划填表
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = max(nums[i] + dp[i + 1][j], nums[j] + dp[i][j - 1])
    
    return dp[0][n - 1]

# 测试
nums = [2, 7, 9, 3, 1]
print(getMaxScore(nums))  # 输出: 22

JavaScript 示例代码

function getMaxScore(nums) {
    const n = nums.length;
    const dp = Array.from({ length: n }, () => Array(n).fill(0));
    
    // 初始化对角线上的值为数组元素本身
    for (let i = 0; i < n; i++) {
        dp[i][i] = nums[i];
    }
    
    // 动态规划填表
    for (let len = 2; len <= n; len++) {
        for (let i = 0; i <= n - len; i++) {
            const j = i + len - 1;
            dp[i][j] = Math.max(nums[i] + dp[i + 1][j], nums[j] + dp[i][j - 1]);
        }
    }
    
    return dp[0][n - 1];
}

// 测试
const nums = [2, 7, 9, 3, 1];
console.log(getMaxScore(nums)); // 输出: 22

// 码小课网站中有更多相关内容分享给大家学习,包括动态规划、算法优化等深入解析。
推荐面试题