494.目标和
494.目标和
题解
题目：给一个数组，和一个target，数组元素可以变正变负，求变号之后，数组元素之和=target的方案数
思路：1动态规划
设满足target的数组中，所有和正数为x，所有和负数为y x+y==target x+y+x-y=target+x-y 因为x-y=所有正数减去所有负数=数组元素和，设为sum 2x=target+sum 所以x=(sum - target) / 2 现在问题就转变为选取若干元素，使得元素之和=x，计算方案数 那么就可以用动态规划来做 dp[i][j]：在前i个元素之中选择，使得元素之和等于j 的方案数 状态转移：dp[i][j] = dp[i-1][j]//不选 j < nums[i] dp[i][j] = dp[i-1][j] + dp[i-1][j-curVal] 方案数=不选+选 j>=nums[i] 初始：dp[0][0] = 1 在前0个元素中选出和为0的方案数 ，只能什么都不选，1中方案 答案：dp[n][neg]
2 暴力dfs，枚举所有情况
func findTargetSumWays(nums []int, target int) int { ans := 0 var dfs func(idx int, cur int) dfs = func(idx int, cur int) { if idx == len(nums) { if cur == target { ans++ } return } dfs(idx+1, cur+nums[idx]) dfs(idx+1, cur-nums[idx]) } dfs(0, 0) return ans }
代码
func findTargetSumWays(nums []int, target int) int { sum, n := 0, len(nums) for _, v := range nums { sum += v } if sum < target || (target+sum)%2 != 0 { return 0 } neg := (sum - target) / 2 dp := make([][]int, n+1) for i := range dp { dp[i] = make([]int, neg+1) } dp[0][0] = 1 for i := 1; i <= n; i++ { for j := 0; j <= neg; j++ { curVal := nums[i-1] if j < curVal { dp[i][j] = dp[i-1][j] //不选 } else { dp[i][j] = dp[i-1][j] + dp[i-1][j-curVal] //方案数=不选数+选方案数 } } } return dp[n][neg] }
