标签： 递归

目标

给你一个非负整数数组 nums 和一个整数 target 。

向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：

输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3

示例 2：

输入：nums = [1], target = 1
输出：1

说明：

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 1000
• 0 <= sum(nums[i]) <= 1000
• -1000 <= target <= 1000

思路

有一个数组，可以在数组元素前加上正负号来组成表达式，问表达式等于target的数目。

如果当前元素为正则累加，否则相减，递归直到所有元素都已列入表达式，如果累加结果等于target则返回1，否则返回0。

//todo 改为递推，或记忆化搜索

代码

/**
 * @date 2024-06-30 20:07
 */
public class FindTargetSumWays494 {
    public int findTargetSumWays(int[] nums, int target) {
        return dfs(nums, 1, nums[0], target) + dfs(nums, 1, -nums[0], target);
    }

    public int dfs(int[] nums, int i, int res, int target) {
        if (i == nums.length) {
            return res - target == 0 ? 1 : 0;
        }
        return dfs(nums, i + 1, res + nums[i], target) + dfs(nums, i + 1, res - nums[i], target);
    }

}

性能

目标

给你一个下标从 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

思路

给定一个数组 nums 与 正整数 x，从下标 0 开始，允许从任意位置 i 开始向后访问位置 j，如果nums[i] 与 nums[j] 的奇偶性相同，则可以获得 nums[j] 分，否则获得 nums[j] - x 分。求能够获得的分数总和的最大值。

刚开始就想到要从后向前，自底向上动态规划，如果当前的奇偶性与与后面的奇偶性相同就累加，否则就将后面的值减去x。接着又想到并不是要每一个节点都要访问，如果节点没有访问奇偶性和谁比较呢？并且后面的得分取决于前一个元素的奇偶性，考虑到昨天的题 子序列最大优雅度，觉得可能方向又错了。

于是就尝试贪心算法，从下标0开始，执行while循环，如果后面的元素奇偶性与之相同，直接累加。对于奇偶性不同的，我们可以考虑累加或者跳过。这样问题就变成了从这个新位置开始向后能获取的最大分数。注意新的位置奇偶性发生了变化。

这么一想问题又变成记忆化搜索了，于是就可以转换为递推/动态规划问题。

// todo 转换为动态规划的写法

代码

/**
 * @date 2024-06-14 8:43
 */
public class MaxScore2786 {

    public long maxScore(int[] nums, int x) {
        int n = nums.length;
        long[][] mem = new long[n + 1][2];
        for (int i = 0; i < mem.length; i++) {
            mem[i] = new long[]{Integer.MIN_VALUE, Integer.MIN_VALUE};
        }
        long res = nums[0];
        int flag = nums[0] % 2;
        int i = 1;
        while (i < n && nums[i] % 2 == flag) {
            res += nums[i];
            i++;
        }
        res += Math.max(0, maxScore(nums, x, i, flag, mem));
        return res;
    }

    public long maxScore(int[] nums, int x, int start, int preFlag, long[][] mem) {
        int n = nums.length;
        if (start >= n) {
            return 0;
        }
        // 如果选择该节点
        int flag = nums[start] % 2;
        long select = nums[start];
        if (preFlag != flag) {
            select -= x;
        }
        int i = start + 1;
        while (i < n && nums[i] % 2 == flag) {
            select += nums[i];
            i++;
        }
        if (mem[i][flag] == Integer.MIN_VALUE) {
            mem[i][flag] = maxScore(nums, x, i, flag, mem);
        }
        select += Math.max(0, mem[i][flag]);
        // 如果跳过该节点
        if (mem[start + 1][preFlag] == Integer.MIN_VALUE) {
            mem[start + 1][preFlag] = maxScore(nums, x, start + 1, preFlag, mem);
        }
        return Math.max(select, mem[start + 1][preFlag]);
    }

}

性能