Link: https://leetcode.com/problems/visit-array-positions-to-maximize-score/description/
## 思路
思路参考[这里](https://leetcode.com/problems/visit-array-positions-to-maximize-score/solutions/3801776/java-c-python-dp-solution/)
一开始想要用jump game的方法做dfs+dp(code见下面) 但由于时间复杂度是$O(N)$ 所以会TLE

## Code

class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        dp = [-inf, -inf]
        dp[nums[0]&1] = nums[0]
        for i in range(1, len(nums)):
            dp[nums[i]&1] = max(dp[nums[i]&1], dp[nums[i]&1^1]-x)+nums[i]
        return max(dp[0], dp[1])

dfs+dp TLE code

class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        dp = [0]*len(nums)
        def dfs(i):
            if dp[i]!=0: return dp[i]
            dp[i] = nums[i]
            for j in range(i+1, len(nums)):
                nextScore = dfs(j)
                if (nums[j]%2==0 and nums[i]%2==1) or (nums[j]%2==1 and nums[i]%2==0):
                    dp[i] = max(dp[i], nums[i]+nextScore-x)
                else: dp[i] = max(dp[i], nums[i]+nextScore)
            return dp[i] 
        return dfs(0)