力扣题解494-目标和

• 题目
• 普通 DP
  • 基础分析
  • 其他说明
  • 解法
• 背包问题
• BMW WARNING

题目

494.目标和
本题可采用 DFS 和 DP 动态规划解法。
此分析 DP

普通 DP

基础分析

• dp 含义

dp[i][t]表示数组索引 i 及之前的数用完得到某个目标值 t 的个数

• 状态转移方程

dp[i][t] = dp[i - 1][t - nums[i]] + dp[i - 1][t + nums[i]]

• 边界条件

nums 第一个数为 0

dp[0][0] = 2

nums 第一个数非零 x

dp[0][x] = dp[0][-x] = 1

其他说明

• 数组代替哈希

可以用哈希来存储上轮循环中得到每个 taget 对应的数量，也可用数组代替。
用数组代替时，sumRet 为源数组 nums 的数值总和，索引 0 处对应的 target 值为-sumRet 的数量，索引 sumRet 处对应的 target 值为 0 的数量。
即存在一个偏移量为 sumRet

• 滚动数组

由状态转移方程可知，数组数值计算可能得到的值位于-sumRet 与 sumRet 之间，故初始化的滚动数组长度为

sumRet * 2 + 1

• 不可到达状态

一个容易想到的状态是：
当 abs(target) > sumRet 时，结论为 0
另外可以排除的状态：
设当 nums 中的值取得 target 时，所有取负值的数绝对值之和为 m
则 所有取正值得数之和为 sumRet - m
有 sumRet - m - m = target
即得

m = (sumRet - target) / 2

由于 m 为整数，故 sumRet - target 为偶数
先行排除不可达状态可优化性能。

解法

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        sumRet = sum(nums)
        if abs(target) > sumRet or (sumRet - target) % 2 != 0:
            return 0

        # 由状态转移方程可知，数组数值计算可能得到的值位于-sumRet与sumRet之间
        notes = [0] * (sumRet * 2 + 1)
        # 初始化非零，注意基础偏移量为sumRet
        notes[sumRet + nums[0]] = notes[sumRet - nums[0]] = 1
        # 初始化零
        if nums[0] == 0:
            # 注意sumRet位置偏移
            notes[sumRet] = 2

        for i in range(1, len(nums)):
            preNotes = notes
            notes = [0] * (sumRet * 2 + 1)
            num = nums[i]
            # 注意遍历结束位置不包含，需要多-1
            for t in range(sumRet, -sumRet-1, -1):
                # 位置偏移
                pos = t + sumRet
                # 超出左边界
                if pos - num < 0:
                    notes[pos] = preNotes[pos + num]
                    continue
                # 超出右边界
                if pos + num > sumRet * 2:
                    notes[pos] = preNotes[pos - num]
                    continue
                # 普通情况
                notes[pos] = preNotes[pos - num] + preNotes[pos + num]
        return notes[target + sumRet]

背包问题

本地有一个更好的动态规划思路，就是转化为背包问题。
上节提到，负数的绝对值和为

sumNegative = (sumRet - target) / 2

同理有取正数之和为

sumPositive = (sumRet + target) / 2

则问题转换为在数组 nums 中，将正数的获取，负数不取，取得值总数为 sumPositive 的解法数。
这是一个标准的背包问题。

• dp 含义

dp[i][s]表示取数组索引 i 及之前的某些数得到某个目标值 s 的方案数

• 状态转移方程

当进行到索引 i 时，此轮得到目标值 s 的方案数取决于 nums[i]取舍。
若不取，dp[i][s] = dp[i - 1][s]
若取，dp[i][s] = dp[i - 1]s - nums[i]]
即有状态转移方程

dp[i][s] = dp[i - 1][s - nums[i]] + dp[i - 1][s]

上述状态转移方程可以看出，外层循环遍历数组时，dp[i]只与 dp[i - 1]有关，故可使用滚动数组记录来代替二维数组节省空间。
同时，在内层循环中，新一轮的值只与滚动数组索引 s 之前的值有关，若采用正向遍历，会覆盖需要读取的值，故采取反向遍历。

• 边界条件

将外层循环第一轮作为边界条件单独处理。
dp[0][0]取值情况为：
nums 第一个数为 0，取得 0 的方案为取或不取皆可

dp[0][0] = 2

nums 第一个数非零 x

dp[0][0] = 1

dp[0][x]取值情况为：
x < sumPositive 时

dp[0][x] = 1

x > sumPositive 时

dp[0][x] = 0

故解法为

class Solution:
    def findTargetSumWays(self, nums: List[int], target: int) -> int:
        sumRet = sum(nums)
        lenNums = len(nums)
        sumPositive = (sumRet + target) // 2
        if abs(target) > sumRet or (sumRet + target) % 2 != 0:
            return 0

        notes = [0] * (sumPositive + 1)

        if nums[0] <= sumPositive:
            notes[nums[0]] = 1

        notes[0] = 2 if nums[0] == 0 else 1

        for i in range(1, lenNums):
            for s in range(sumPositive, nums[i]-1, -1):
                notes[s] = notes[s] + notes[s - nums[i]]

        return notes[-1]

BMW WARNING

• Bulletin

本文首发于 skyline.show 欢迎访问，
文章实时更新，如果有什么错误或不严谨之处望请指出，十分感谢。
如果你觉得有用，欢迎到Github仓库点亮⭐️。

I am a bucolic migant worker but I never walk backwards.

• Material

参考资料如下列出，部分引用可能遗漏或不可考，侵删。

63.不同路径-ii

• Warrant

本文作者： Skyline(lty)

文章链接：http://www.skyline.show/力扣题解 63-不同路径-ii.html

授权声明： 本博客所有文章除特别声明外， 均采用 CC BY - NC - SA 3.0 协议。 转载请注明出处！