題目描述：

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

給每個元素的前面匹配上+或者—讓最后的結(jié)果序列和為S

法一：腦海里第一反應(yīng)是用遞歸的方法：

算法書上86頁，不確定是不是用這樣的方法。下機(jī)調(diào)試下。。。。

分界線-------------------------------------------------------------------開始抄襲了

法一：

這道題給了我們一個數(shù)組，和一個目標(biāo)值，讓我們給數(shù)組中每個數(shù)字加上正號或負(fù)號，然后求和要和目標(biāo)值相等，求有多少中不同的情況。那么對于這種求多種情況的問題，我最想到的方法使用遞歸來做。我們從第一個數(shù)字，調(diào)用遞歸函數(shù)，在遞歸函數(shù)中，分別對目標(biāo)值進(jìn)行加上當(dāng)前數(shù)字調(diào)用遞歸，和減去當(dāng)前數(shù)字調(diào)用遞歸，這樣會涵蓋所有情況，并且當(dāng)所有數(shù)字遍歷完成后，我們看若目標(biāo)值為0了，則結(jié)果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);//其實(shí)一直都不清楚遞歸的調(diào)用過程。 } };
對遞歸進(jìn)行了優(yōu)化，使用dp數(shù)組來記錄中間值，這樣可以避免重復(fù)運(yùn)算，，于是誕生了法二
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數(shù)組，其中dp[i][j]表示到第i-1個數(shù)字且和為j的情況總數(shù)，參見代碼
法三：
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]; } };

我們也可以對上面的方法進(jìn)行空間上的優(yōu)化，只用一個哈希表，而不是用一個數(shù)組的哈希表，我們在遍歷數(shù)組中的每一個數(shù)字時，
新建一個哈希表，我們在遍歷原哈希表中的項時更新這個新建的哈希表，最后把新建的哈希表整個賦值和原哈希表，參見代碼如下： 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]; } };

動態(tài)規(guī)劃 狀態(tài)轉(zhuǎn)移方程：dp[i + 1][k + nums[i] * sgn] += dp[i][k]上式中，sgn取值±1，k為dp[i]中保存的所有狀態(tài)；初始令dp[0][0] = 1利用滾動數(shù)組，可以將空間復(fù)雜度優(yōu)化到O(n)，n為可能的運(yùn)算結(jié)果的個數(shù) 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]

?

轉(zhuǎn)載于:https://www.cnblogs.com/maowuyu-xb/p/6416864.html

總結(jié)

以上是生活随笔為你收集整理的动态规划--目标和问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。