首页 > 代码库 > 动态规划--目标和问题

动态规划--目标和问题

题目描述:

You are given a list of non-negative integers, a1, a2, ..., an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.

Find out how many ways to assign symbols to make sum of integers equal to target S

给每个元素的前面匹配上+或者—让最后的结果序列和为S

法一:脑海里第一反应是用递归的方法:

算法书上86页,不确定是不是用这样的方法。下机调试下。。。。

分界线-------------------------------------------------------------------开始抄袭了

法一:

这道题给了我们一个数组,和一个目标值,让我们给数组中每个数字加上正号或负号,然后求和要和目标值相等,求有多少中不同的情况。那么对于这种求多种情况的问题,我最想到的方法使用递归来做。我们从第一个数字,调用递归函数,在递归函数中,分别对目标值进行加上当前数字调用递归,和减去当前数字调用递归,这样会涵盖所有情况,并且当所有数字遍历完成后,我们看若目标值为0了,则结果res自增1,参见代码如下:

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int res = 0;
        helper(nums, S, 0, res);
        return res;
    }
    void helper(vector<int>& nums, int S, int start, int& res) {
        if (start >= nums.size()) {
            if (S == 0) ++res;
            return;
        }
        helper(nums, S - nums[start], start + 1, res);
        helper(nums, S + nums[start], start + 1, res);//其实一直都不清楚递归的调用过程。
    }
};
对递归进行了优化,使用dp数组来记录中间值,这样可以避免重复运算,,于是诞生了法二
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        vector<unordered_map<int, int>> dp(nums.size());
        return helper(nums, S, 0, dp);
    }
    int helper(vector<int>& nums, int sum, int start, vector<unordered_map<int, int>>& dp) {
        if (start == nums.size()) return sum == 0;
        if (dp[start].count(sum)) return dp[start][sum];
        int cnt1 = helper(nums, sum - nums[start], start + 1, dp);
        int cnt2 = helper(nums, sum + nums[start], start + 1, dp);
        return dp[start][sum] = cnt1 + cnt2;
    }
};
我们也可以使用迭代的方法来解,还是要用dp数组,其中dp[i][j]表示到第i-1个数字且和为j的情况总数,参见代码
法三:
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        int n = nums.size();
        vector<unordered_map<int, int>> dp(n + 1);
        dp[0][0] = 1;
        for (int i = 0; i < n; ++i) {
            for (auto &a : dp[i]) {
                int sum = a.first, cnt = a.second;
                dp[i + 1][sum + nums[i]] += cnt;
                dp[i + 1][sum - nums[i]] += cnt;
            }
        }
        return dp[n][S];
    }
};

我们也可以对上面的方法进行空间上的优化,只用一个哈希表,而不是用一个数组的哈希表,我们在遍历数组中的每一个数字时,
新建一个哈希表,我们在遍历原哈希表中的项时更新这个新建的哈希表,最后把新建的哈希表整个赋值和原哈希表,参见代码如下:
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int S) {
        unordered_map<int, int> dp;
        dp[0] = 1;
        for (int num : nums) {
            unordered_map<int, int> t;
            for (auto a : dp) {
                int sum = a.first, cnt = a.second;
                t[sum + num] += cnt;
                t[sum - num] += cnt;
            }
            dp = t;
        }
        return dp[S];
    }
};


动态规划
状态转移方程:dp[i + 1][k + nums[i] * sgn] += dp[i][k]

上式中,sgn取值±1,k为dp[i]中保存的所有状态;初始令dp[0][0] = 1

利用滚动数组,可以将空间复杂度优化到O(n),n为可能的运算结果的个数
class Solution(object):
    def findTargetSumWays(self, nums, S):
        """
        :type nums: List[int]
        :type S: int
        :rtype: int
        """
        dp = collections.Counter()
        dp[0] = 1
        for n in nums:
            ndp = collections.Counter()
            for sgn in (1, -1):
                for k in dp.keys():
                    ndp[k + n * sgn] += dp[k]
            dp = ndp
        return dp[S]

 

动态规划--目标和问题