动态规划07-目标和

2023-12-28 04:29:17

题目介绍

给定一个非负整数数组,a1, a2, …, an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

思路分析

本题跟简单的01背包问题有所不同,本题要求解的是实现装满背包的可能种类,所以本质上是一个排列问题。对于每个元素,只有加和减两种可能,最终要实现的就是让和是S,这里给出数学公式,假设将整个数组分成两个部分,一个是正数部分,另一个是负数部分的绝对值,两个部分的和是Sum,两个部分的差值就是S,将两个式子联立就能解出其中的一个部分的值是(S+Sum)/2。背包问题初具雏形!

  1. 定义dp[j]的含义:填满容积为j的背包的方法有dp[j]种。
  2. 确定转换关系:dp[j] += dp[j - sums[i]],解释一下就是对于容积为j的包,当遍历到物品i的时候,其方法就是之前的方法(去掉sum[i]的容量的包的可能种类)加上当前的方法。
  3. dp数组初始化:将dp[j]初始化我为1
  4. 遍历顺序:nums内,targets外,同时内层循环倒序遍历
  5. 举例推导成立

代码

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) sum += nums[i];
        if (abs(S) > sum) return 0; // 此时没有方案
        if ((S + sum) % 2 == 1) return 0; // 此时没有方案
        int bagSize = (S + sum) / 2;
        vector<int> dp(bagSize + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = bagSize; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bagSize];
    }
};

文章来源:https://blog.csdn.net/weixin_73074012/article/details/135257309
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。