LeetCode 移掉石头赢得游戏题解

LeetCode 移掉石头赢得游戏题解题目描述给定一堆石头你和对手轮流移除石头。每次可以移除 1 到 k 颗石头。计算你能获得的最大分数。示例输入nums [1, 2, 3, 1],k 2输出10解题思路方法动态规划思路使用动态规划dp[i] 表示考虑到第 i 堆石头能获得的最大分数。dp[i] max(dp[i-j] sum(nums[i-j1:i1])) for j in 1..k。复杂度分析时间复杂度O(n * k)。空间复杂度O(n)。代码实现def remove_stones(nums, k): n len(nums) dp [0] * n prefix_sum [0] * (n 1) for i in range(n): prefix_sum[i 1] prefix_sum[i] nums[i] for i in range(n): for j in range(1, min(k, i 1) 1): score prefix_sum[i 1] - prefix_sum[i 1 - j] dp[i] max(dp[i], (dp[i - j] if i j else 0) score) return dp[n - 1] # 测试 def test_remove_stones(): nums [1, 2, 3, 1] k 2 print(remove_stones(nums, k)) # 输出10 if __name__ __main__: test_remove_stones()总结移掉石头赢得游戏是动态规划的典型应用通过遍历所有可能的移除方案来计算最大分数。