心路历程这道题的递推关系很明显类似于一个背包问题按照背包问题的建模方式即可。状态从头开始以nums[i]结尾的子数组当前目标和动作选择加号还是减号返回值有多少种可能的组合解法动态规划递归动态规划-建议classSolution:deffindTargetSumWays(self,nums:List[int],target:int)-int:# dp问题cachedefdp(i,targeti):ifi0:returnint(targetinums[0])int(targeti-nums[0])returndp(i-1,targeti-nums[i])dp(i-1,targetinums[i])returndp(len(nums)-1,target)数组动态规划-用偏移量解决负索引问题fromtypingimportListclassSolution:deffindTargetSumWays(self,nums:List[int],target:int)-int:total_sumsum(nums)# 如果目标超出可能范围直接返回0ifabs(target)total_sum:return0# 偏移量将负数索引映射到非负索引offsettotal_sum# dp[j] 表示当前考虑过的数字能组成和为 (j - offset) 的方法数dp[0]*(2*total_sum1)dp[offset]1# 和为0有一种方式还没选任何数字fornuminnums:new_dp[0]*(2*total_sum1)forsum_valinrange(-total_sum,total_sum1):idxsum_valoffsetifdp[idx]0:continue# 加号new_idx_plussum_valnumoffsetif0new_idx_pluslen(dp):new_dp[new_idx_plus]dp[idx]# 减号new_idx_minussum_val-numoffsetif0new_idx_minuslen(dp):new_dp[new_idx_minus]dp[idx]dpnew_dpreturndp[targetoffset]