力扣每日一题 6/14 动态规划+数组

2786.访问数组中的位置使分数最大【中等】

题目：

给你一个下标从 0 开始的整数数组 nums 和一个正整数 x 。

你 一开始 在数组的位置 0 处，你可以按照下述规则访问数组中的其他位置：

• 如果你当前在位置 i ，那么你可以移动到满足 i < j 的 任意 位置 j 。
• 对于你访问的位置 i ，你可以获得分数 nums[i] 。
• 如果你从位置 i 移动到位置 j 且 nums[i] 和 nums[j] 的 奇偶性 不同，那么你将失去分数 x 。

请你返回你能得到的 最大 得分之和。

注意 ，你一开始的分数为 nums[0] 。

示例 1：

输入：nums = [2,3,6,1,9,2], x = 5

输出：13

解释：我们可以按顺序访问数组中的位置：0 -> 2 -> 3 -> 4 。

对应位置的值为 2 ，6 ，1 和 9 。因为 6 和 1 的奇偶性不同，所以下标从 2 -> 3 让你失去 x = 5 分。

总得分为：2 + 6 + 1 + 9 - 5 = 13 。

示例 2：

输入：nums = [2,4,6,8], x = 3

输出：20

解释：数组中的所有元素奇偶性都一样，所以我们可以将每个元素都访问一次，而且不会失去任何分数。

总得分为：2 + 4 + 6 + 8 = 20 。

提示：

• 2 <= nums.length <= 10**5
• 1 <= nums[i], x <= 10**6

分析问题：

• 这是一个动态规划问题，需要考虑在每个位置上能获得的最大得分。
• 关键在于判断移动到下一个位置时是否会因为奇偶性不同而失去分数 x，并在此基础上计算最大得分。

解题方案：

1. 定义一个二维数组 dp[i][0] 和 dp[i][1] ，分别表示在位置 i 且当前数字为奇数或偶数时能获得的最大得分。
2. 初始化 dp[0][0] = nums[0] （如果 nums[0] 为偶数），dp[0][1] = nums[0] （如果 nums[0] 为奇数）。
3. 从位置 1 开始遍历数组 nums ：

• 如果 nums[i] 为偶数：

• dp[i][0] = max(dp[i - 1][0] + nums[i], dp[i - 1][1] + nums[i] - x)
• dp[i][1] = dp[i - 1][1]

• 如果 nums[i] 为奇数：

• dp[i][1] = max(dp[i - 1][1] + nums[i], dp[i - 1][0] + nums[i] - x)
• dp[i][0] = dp[i - 1][0]

4. 最终的最大得分即为 max(dp[n - 1][0], dp[n - 1][1]) ，其中 n 是数组 nums 的长度。

代码实现：

from functools import cache
class Solution:
    def maxScore(self, nums: List[int], x: int) -> int:
        @cache
        def dfs(i,j):
            if i == len(nums): return 0
            if nums[i] % 2 != j: return dfs(i+1,j)
            return max(dfs(i+1,j),dfs(i+1,j^1)-x)+nums[i]
        return dfs(0,nums[0]%2)

总结：

          利用 functools 模块中的 cache 装饰器对 dfs 函数进行缓存优化，避免重复计算。

   dfs 函数接受两个参数 i 和 j ，分别表示当前在数组 nums 中的位置和当前数字的奇偶性标志（0 表示偶数，1 表示奇数）。

       函数首先判断如果当前位置 i 达到数组末尾，返回 0 。

       如果当前数字的奇偶性与 j 不一致，直接返回下一个位置且奇偶性不变时的结果，即 dfs(i + 1, j) 。

       否则，返回两种可能情况中的最大值：一是直接移动到下一个位置且奇偶性不变时的结果 dfs(i + 1, j) ，二是移动到下一个位置且奇偶性改变时减去 x 再加上当前数字 nums[i] 的结果 dfs(i + 1, j ^ 1) - x + nums[i] 。

       最终，通过调用 dfs(0, nums[0] % 2) 来计算并返回最大得分。

这道题考察的内容包括：

1. 对动态规划思想的理解和应用，需要找到最优的决策路径来获得最大得分。
2. 对函数递归调用的掌握，通过递归的方式遍历所有可能的移动情况。
3. 对奇偶性判断和处理的能力，根据数字的奇偶性做出不同的决策。
4. 对缓存装饰器的运用，优化函数的性能，避免重复计算。

从这道题中可以学到：

1. 深入理解动态规划的解题思路，学会如何定义状态和状态转移方程来解决最优解问题。

• 例如，通过定义 dp[i][0] 和 dp[i][1] 来表示不同奇偶性下的最大得分。

2. 掌握递归函数的设计和编写，清晰地定义递归的终止条件和递归逻辑。

• 像本题中的 dfs 函数，通过递归探索所有可能的位置移动情况。

3. 提升对数字奇偶性的处理能力，灵活运用奇偶性来制定策略。

• 依据数字的奇偶性决定是否扣除分数 x 。

4. 认识到缓存装饰器的作用和优势，学会在适当的场景中运用缓存来提高程序的效率。

• 利用 @cache 避免重复计算相同参数的 dfs 结果。

“所谓宿命，其实都是最好的安排。”——《将夜》