Py学习  »  Python

每日一道算法题--leetcode 486-- 预测赢家(动态规划)--python

杉杉不要bug • 4 年前 • 422 次点击  
阅读 13

每日一道算法题--leetcode 486-- 预测赢家(动态规划)--python

【题目描述】

【思路】

这种取数,预测赢家的题目,是共通的。采用动态规划法。每次只需要考虑是取左侧的还是右侧的,用一个二维数组保存起来取左侧和取右侧会产生的最大差值。如何选择select(i,j)只和select(i+1,j)和select(i,j-1)有关,因此为了避免重复计算,肯定是要自底向上,就考虑递归实现。

【代码】

class Solution(object):
    def PredictTheWinner(self, nums):
        n=len(nums)
        dp=[[0]*n for _ in range(n)]
        def selectNumber(l,r):
            if l==r: 
                return nums[l]
            if dp[l][r]>0:
                return dp[l][r]
            dp[l][r]=max(nums[l]-selectNumber(l+1,r),nums[r]- selectNumber(l,r-1))
            return dp[l][r]
        return True if selectNumber(0,n-1)>=0 else False
复制代码
Python社区是高质量的Python/Django开发社区
本文地址:http://www.python88.com/topic/34551
 
422 次点击