494. 目标和

这篇具有很好参考价值的文章主要介绍了494. 目标和。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

原题链接:

494. 目标和

https://leetcode.cn/problems/target-sum/description/

完成情况:

494. 目标和,# LeetCode题解,算法知识,java学习,代理模式,java,leetcode

解题思路:

数组回溯法

backTrack(nums, target, index+1, curSum+nums[index]);
backTrack(nums, target, index+1, curSum-nums[index]);

动态规划

	 假设P是正子集,N是负子集 例如: 假设nums = [1, 2, 3, 4, 5],target = 3,一个可能的解决方案是+1-2+3-4+5 = 3 这里正子集P = [1, 3, 5]和负子集N = [2, 4]
	 sum(P) - sum(N) = target
	 sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
	 2 * sum(P) = target + sum(nums)
	 因此,原来的问题已转化为一个求子集的和问题: 找到nums的一个子集 P,使得sum(P) = (target + sum(nums)) / 2,该式已经证明了target + sum(nums)必须是偶数,否则无解
	 求子集的问题可以转化为01背包问题
	 定义二维数组dp,其中dp[i][j]表示在数组下标为0...i的元素中任选元素,使得这些元素之和等于j的方案数

494. 目标和,# LeetCode题解,算法知识,java学习,代理模式,java,leetcode

494. 目标和,# LeetCode题解,算法知识,java学习,代理模式,java,leetcode

参考代码:

数组回溯法

package 西湖算法题解___中等题;

public class __494目标和__数组回溯法 {
	int res = 0;
	public int findTargetSumWays(int[] nums, int target) {
		backTrack(nums,target,0,0);
		return res;
	}

	/**
	 *
	 * @param nums      数组
	 * @param target    目标值
	 * @param index     索引位置
	 * @param curSum    当前累计和
	 */
	private void backTrack(int[] nums, int target, int index, int curSum) {
		//1 <= nums.length <= 20
		//这种方法,属于递归,完全是因为数量级太小了
		//不然肯定算不出来的。
		if (index == nums.length){      //所有元素已经遍历完了
			if (curSum == target){
				res++;
			}
		}else{
			backTrack(nums, target, index+1, curSum+nums[index]);
			backTrack(nums, target, index+1, curSum-nums[index]);
		}
	}


}

__494目标和__动态规划

package 西湖算法题解___中等题;

public class __494目标和__评论区大佬 {
	/**
	 题目介绍:
	    就是说有一个数组,然后要在数组任意两两元素间插入一个【+】或者【-】
	    最终要构成target这个值,
	        问你有多少种拼接情况。
	 */
	public int findTargetSumWays(int[] nums, int target) {
		//很明显的一道dp题目,最终结果取决于过程叠加。
		/**
		 假设P是正子集,N是负子集 例如: 假设nums = [1, 2, 3, 4, 5],target = 3,一个可能的解决方案是+1-2+3-4+5 = 3 这里正子集P = [1, 3, 5]和负子集N = [2, 4]
		 sum(P) - sum(N) = target
		 sum(P) + sum(N) + sum(P) - sum(N) = target + sum(P) + sum(N)
		 2 * sum(P) = target + sum(nums)
		 因此,原来的问题已转化为一个求子集的和问题: 找到nums的一个子集 P,使得sum(P) = (target + sum(nums)) / 2,该式已经证明了target + sum(nums)必须是偶数,否则无解
		 求子集的问题可以转化为01背包问题
		 定义二维数组dp,其中dp[i][j]表示在数组下标为0...i的元素中任选元素,使得这些元素之和等于j的方案数
		 */
		int nLength = nums.length;
		//先去掉点特殊情况
		int sum = 0;
		for (int num:nums){
			sum += num;
		}
		// target + sum(nums)必须是偶数,否则无解     //要使target = nums[]的加减操作合,则它们必须同奇或者同偶
		// Math.abs(target) <= sum才有解       //目标值不能比绝对值求和还大
		//偶数判断还可以用   (lambda & 1) == 1   去判断
		if (((sum + target) & 1) == 1 || Math.abs(target) > sum){
			return 0;
		}
		int size = (sum + target) / 2;

		// 定义二维数组dp,其中dp[i][j]表示在数组下标为0...i的元素中任选元素,使得这些元素之和等于j的方案数
		int dp_findTargetSumWays [][] = new int[nLength][size+1];
		// 对dp[0][j]的初始化:除dp[0][0]和dp[0][nums[0]]外全部初始化为0
		// dp[0][0] = 1:nums[0]不为0时,此时dp[0][0]和dp[0][nums[0]]不重合,只有不选nums[0],其总和为0
		// dp[0][0] = 2:nums[0]为0时,此时dp[0][0]和dp[0][nums[0]]重合,选或者不选nums[0],其总和都为0
		if (nums[0] <= size){
			dp_findTargetSumWays[0][nums[0]] = 1;
		}
		if (nums[0] == 0){
			dp_findTargetSumWays[0][0] = 2;
		}else {
			dp_findTargetSumWays[0][0] = 1;
		}

		// 对dp[i][0]的初始化,可以放在下面整个dp的递推代码中
		for (int i = 1;i<nLength;i++){
			if (nums[i] == 0){
				//当nums[1]为0时,选择或者不选择nums[1]都可以使总和为0,
				//即dp[i][0] = dp[i - 1][0] + dp[i - 1][0 - nums[i]] = 2 * dp[i -1][0]
				dp_findTargetSumWays[i][0] = 2*dp_findTargetSumWays[i-1][0];
			}else{
				// 当nums[i]不为0时,只有不选nums[i]才可以使总和为0
				dp_findTargetSumWays[i][0] = dp_findTargetSumWays[i-1][0];
			}
		}
		// dp[i][j]递推:由于初始化时都将i = 0和j = 0的情况已经赋值,所以直接从i = 1和j = 1开始
		// 完全可以将上面对dp[i][0]的初始化放在此处,只需要将j从0开始
		for (int i=1;i<nLength;i++){
			for (int j=1;j<=size;j++){
				if (j>=nums[i]){
					dp_findTargetSumWays[i][j] = dp_findTargetSumWays[i-1][j] + dp_findTargetSumWays[i-1][j-nums[i]];
				}else{
					dp_findTargetSumWays[i][j] = dp_findTargetSumWays[i-1][j];
				}
			}
		}
		return dp_findTargetSumWays[nLength-1][size];
	}
}

经验吸取

  1. 首先,如果最终结果可以由其中的每一步过程,造成影响得来,那么就可以考虑用dp

  2. dp的难点就在于状态转移方程!!!如何将一个问题转化很重要!!!

  3. 转化形式应该为:
    494. 目标和,# LeetCode题解,算法知识,java学习,代理模式,java,leetcode
    未知状态 = 已知确定目标值
    494. 目标和,# LeetCode题解,算法知识,java学习,代理模式,java,leetcode

    dp数组过程推演情况。文章来源地址https://www.toymoban.com/news/detail-655758.html

到了这里,关于494. 目标和的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • LeetCode - 494 目标和

    目录 题目来源 题目描述 示例 提示 题目解析 算法源码 题目来源 494. 目标和 - 力扣(LeetCode) 题目描述 给你一个整数数组 nums 和一个整数 target 。 向数组中的每个整数前添加 \\\'+\\\' 或 \\\'-\\\' ,然后串联起所有整数,可以构造一个 表达式 : 例如,nums = [2, 1] ,可以在 2 之前添加

    2024年02月12日
    浏览(39)
  • 【LeetCode】494. 目标和

    首先,将这道题想成 0-1背包问题 ,我们最终要输出的结果是最多的方法数,因此 dp 数组需要记录具体的方法数。 状态定义 按照 0-1 背包问题的套路,我们将状态定义为 : dp[i][j] ,表示「前 i 个数字,和等于 j 的情况下,能够达到的不同表达式的最大数目」。 状态转移方程

    2024年02月03日
    浏览(35)
  • 动态规划 Leetcode 494 目标和

    Leetcode 494 学习记录自代码随想录 要点:1.想到±代表其实求的是连个组合的差值,进而记left为正组合,right为负组合,则有 { l e f t − r i g h t = t a r g e t l e f t + r i g h t = s u m left { begin{matrix} left-right=target \\\\ left+right=sum end{matrix} right . { l e f t − r i g h t = t a r g e t l e f t + r

    2024年04月09日
    浏览(61)
  • Day43|leetcode 1049.最后一块石头的重量II、494.目标和、474.一和零

    题目链接:1049. 最后一块石头的重量 II - 力扣(LeetCode) 视频链接:动态规划之背包问题,这个背包最多能装多少?LeetCode:1049.最后一块石头的重量II_哔哩哔哩_bilibili 有一堆石头,每块石头的重量都是正整数。 每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设

    2024年02月10日
    浏览(51)
  • [Leetcode] 416. 分割等和子集、1049. 最后一块石头的重量 II、494. 目标和、474. 一和零

    内容:今天复习下dp数组中的背包问题 分割等和子集 - 能否装满 最后一块石头 - 尽可能装满 目标和 - 有多少种方法装 一和零 - 装满背包有多少个物品 416. 分割等和子集 10背包:用/不用;有容量;有价值 dp[j] : 容量为j,最大价值为dp[j]         重量和价值等价 dp[target] == t

    2024年02月16日
    浏览(43)
  • 【LeetCode题目详解】第九章 动态规划 part05 1049. 最后一块石头的重量 II 494. 目标和 474.一和零(day43补)

    有一堆石头,用整数数组  stones 表示。其中  stones[i] 表示第 i 块石头的重量。 每一回合,从中选出 任意两块石头 ,然后将它们一起粉碎。假设石头的重量分别为  x 和  y ,且  x = y 。那么粉碎的可能结果如下: 如果  x == y ,那么两块石头都会被完全粉碎; 如果  x != y

    2024年02月09日
    浏览(38)
  • 算法训练第四十三天|1049. 最后一块石头的重量 II 、494. 目标和、474.一和零

    题目链接:1049. 最后一块石头的重量 II 参考:https://programmercarl.com/1049.%E6%9C%80%E5%90%8E%E4%B8%80%E5%9D%97%E7%9F%B3%E5%A4%B4%E7%9A%84%E9%87%8D%E9%87%8FII.html 题目难度:中等 有一堆石头,每块石头的重量都是正整数。 每一回合,从中选出任意两块石头,然后将它们一起粉碎。假设石头的重量分

    2023年04月09日
    浏览(38)
  • 代码随想录Day36 动态规划05 LeetCode T1049最后一块石头的重量II T494 目标和 T474 一和零

    理论基础  : 代码随想录Day34 LeetCode T343整数拆分 T96 不同的二叉搜索树-CSDN博客 1.明白dp数组的含义 2.明白递推公式的含义 3.初始化dp数组 4.注意dp数组的遍历顺序 5.打印dp数组排错 题目链接:1049. 最后一块石头的重量 II - 力扣(LeetCode) 这题我们仍然采用动规五部曲来写,这题和

    2024年02月06日
    浏览(41)
  • 494. 目标和

    494. 目标和 https://leetcode.cn/problems/target-sum/description/ 首先,如果最终结果可以由其中的每一步过程,造成影响得来,那么就可以考虑用dp dp的难点就在于状态转移方程!!!如何将一个问题转化很重要!!! 转化形式应该为: 未知状态 = 已知确定目标值 dp数组过程推演情况。

    2024年02月12日
    浏览(49)
  • 【LeetCode算法系列题解】第61~65题

    【题目描述】 给你一个链表的头节点 head ,旋转链表,将链表每个节点向右移动 k 个位置。 【示例1】 【示例2】 【提示】 链表中节点的数目在范围 [0, 500] 内 − 100 ≤ N o d e . v a l ≤ 100 -100le Node.valle 100 − 100 ≤ N o d e . v a l ≤ 100 0 ≤ k ≤ 2 ∗ 1 0 9 0le kle 2 * 10^9 0 ≤ k ≤

    2024年02月09日
    浏览(36)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包