2022.01.16 - SX10-16.目标和

news/2024/10/30 11:26:57/

文章目录

  • 1. 题目
  • 2. 思路
    • (1) 动态规划
    • (2) 动态规划优化
  • 3. 代码

1. 题目

在这里插入图片描述

2. 思路

(1) 动态规划

  • 这道题可以转化为0/1背包问题,由于总和sum和目标和target已经确定,因此,要求的即是从数组中挑出和为(sum-target)/2的方案数。
  • 首先确定动态规划数组的含义,dp[i][j]表示从下标为[0,i)的元素中挑出和为j的方案数,初始化时令dp[0][0]=1即可。
  • 若nums[i-1]>j,则必然不取nums[i-1],因此,dp[i][j]=dp[i-1][j];否则,dp[i][j]=dp[i-1][j]+dp[i-1][j-nums[i-1]],即从下标为[0,i-1)的元素中挑出和为j和j-nums[i-1]的方案数之和。

(2) 动态规划优化

  • 状态压缩后,dp[i]表示从数组中挑出和为i的方案数。

3. 代码

public class Test {public static void main(String[] args) {}
}class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for (int num : nums) {sum += num;}if (sum < target) {return 0;}int differ = sum - target;if ((differ & 1) == 1) {return 0;}target = differ >> 1;int n = nums.length;int[][] dp = new int[n + 1][target + 1];dp[0][0] = 1;for (int i = 1; i <= n; i++) {for (int j = 0; j <= target; j++) {if (nums[i - 1] > j) {dp[i][j] = dp[i - 1][j];} else {dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];}}}return dp[n][target];}
}class Solution1 {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for (int num : nums) {sum += num;}if (sum < target) {return 0;}int differ = sum - target;if ((differ & 1) == 1) {return 0;}target = differ >> 1;int n = nums.length;int[] dp = new int[target + 1];dp[0] = 1;for (int i = 0; i < n; i++) {for (int j = target; j >= nums[i]; j--) {dp[j] += dp[j - nums[i]];}}return dp[target];}
}

http://www.ppmy.cn/news/155040.html

相关文章

2022.01.18 - SX10-21.组合总和 Ⅳ

文章目录 1. 题目2. 思路(1) 动态规划 3. 代码 1. 题目 2. 思路 (1) 动态规划 动态规划数组dp[i]表示总和为i的组合的个数&#xff0c;初始化时&#xff0c;dp[0]1。对于总和为i-num的每一种排列&#xff0c;在最后添加num后即可得到总和为i的排列&#xff0c;因此&#xff0…

2022.01.19 - SX10-22.爬楼梯

文章目录 1. 题目2. 思路(1) 动态规划 3. 代码 1. 题目 2. 思路 (1) 动态规划 动态规划数组dp[i]表示爬到第i个台阶的方案数&#xff0c;累加最后一步的所有方案数即可。注意&#xff01;转化为完全背包问题即为容量在外&#xff0c;物品在内。 3. 代码 public class Test …

2022.02.13 - SX10-30.打家劫舍 II

文章目录 1. 题目2. 思路(1) 动态规划 3. 代码 1. 题目 2. 思路 (1) 动态规划 由于第一家和最后一家只能选择一家偷&#xff0c;另一家必然不能偷&#xff0c;因此&#xff0c;可以直接删除第一家或者最后一家&#xff0c;这样就断开了环&#xff0c;分别进行动态规划&#x…

IV XXSC-11

文章目录 展示管理员列表CV代码说明通过管理员列表页面,删除管理员管理员权限实际操作步骤如下 事务 展示管理员列表 删除数据后可以选择本地删除,而无需重新请求服务器获取数据,这样可以不占用网络和服务器资源 但是也存在问题,就是别的用户在访问,你没及时删除,看到的是假的…

【回答问题】ChatGPT上线了!给我推荐20个比较流行的深度学习模型

目录 给我推荐20个比较流行的nlp模型给我推荐20个比较流行的计算机视觉模型给我推荐20个比较流行的图像分类模型给我推荐20个比较流行的人脸识别模型给我推荐20个比较流行的实体识别模型给我推荐20个比较流行的语言识别模型给我推荐20个比较流行的激光雷达3D点云模型给我推荐20…

XDS110(TMDSEMU110-U)

XDS110&#xff08;TMDSEMU110-U&#xff09; 1. 探针资源 XDS110探针支持许多用于主机和目标通信的接口。 主机探测通信 USB 2.0设备与HS USB PHY 用于UART支持的USB通信设备类协议 标准USB批量IN和OUT端点支持TI自定义协议 探测目标通信 ieee1149.1 jtag IEEE 1149.7 cJTA…

XSD 指示器概述

通过指示器&#xff0c;我们可以控制在文档中使用元素的方式。 指示器 有七种指示器&#xff1a; Order 指示器&#xff1a; AllChoiceSequence Occurrence 指示器&#xff1a; maxOccursminOccurs Group 指示器&#xff1a; Group nameattributeGroup name Order 指示…

2022.01.17 - SX10-17.一和零

文章目录 1. 题目2. 思路(1) 动态规划 3. 代码 1. 题目 2. 思路 (1) 动态规划 定义三维动态规划数组dp&#xff0c;dp[i][j][k]表示在前i个字符串中&#xff0c;最多有j个0、k个1的情况下&#xff0c;所能包含的最大字符串数量。初始化时&#xff0c;dp[0][j][k]0。若不选第i…