LeetCode-day12-2786. 访问数组中的位置使分数最大

LeetCode-day12-2786. 访问数组中的位置使分数最大

• 题目描述
• 示例
• • 示例1：
  • 思路
  • 代码

    题目描述

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

    
    （图片来源网络，侵删）

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

    如果你当前在位置 i ，那么你可以移动到满足 i

    对于你访问的位置 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 。

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

    输出：20

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

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

    思路

    采用记忆化搜索。

    • 如果一个状态（递归入参）是第一次遇到，那么可以在返回前，把状态及其结果记到一个 memo 数组中。
    • 如果一个状态不是第一次遇到（memo 中保存的结果不等于 memo 的初始值），那么可以直接返回 memo 中保存的结果。

      代码

       public long maxScore(int[] nums, int x) {
              int n = nums.length;
              long[][] meno = new long[n][2];
              for (long[] row : meno) {
                  Arrays.fill(row,-1);
              }
              return dfs(0,nums[0]%2,nums,x,meno);
          }
          private long dfs(int i, int j, int[] nums, int x, long[][] meno) {
              if (i == nums.length){
                  return 0;
              }
              if (meno[i][j] != -1){
                  return meno[i][j];
              }
              if (nums[i] % 2 != j){
                  return meno[i][j]  = dfs(i+1,j,nums,x,meno);
              }
              long res1 = dfs(i+1,j,nums,x,meno);
              long res2 = dfs(i+1,j^1,nums,x,meno);
              return meno[i][j]  =Math.max(res1,res2-x)+nums[i];
          }