這篇page是針對leetcode上的494.目標和所寫的。小尼先簡單的說明一下這道題的意思，就是給出一個整數數組nums和一個整數target，需要向數組中的每個整數前添加'+'或者'-'，然后串聯起所有整數，可以構造一個表達式，返回可以通過上述方法構造的、運算結果等于target的不同表達式的數目。

首先呢小尼先簡單的說明一下這道題的解題思路，我們不要把這道題想的過于復雜，也不要將這道題想的過于簡單，其實這里可以寫+也可以寫-，其實無非就是構造成正數或者是負數，其實就是我們構造兩個數組進行對應的賦值即可，一個數組里面全部都是賦值正數，另一個里面全部都是賦值負數。我們如果將所有的正數數組都定義為left，所有的負數數組都定義為right，那么我們定義一個sum=left+right，left-(sum-left)=target，那么我們通過上述三個式子我們可以推出一個結論就是，left=(target+sum)/2,然后我們需要的是滿足為target的組合，其實就直接轉換成了0-1背包問題，裝滿容器為x背包，有幾種方法。

小尼接下來繼續說明一下動態規劃五部曲：

1、確定dp數組以及下標的含義：dp[j]表示：填滿j(包括j)這么大容積的包，有dp[j]種方法

2、確定遞推公式：當我們考慮到nums[i]的話，湊成dp[j]就有dp[j]-nums[i]種方法，這里其實就是類似于一個累加起來的方法

dp[j] += dp[j - nums[i]]

3、dp數組如何進行初始化：從遞歸公式我們可以看出，在初始化的時候dp[0]一定要初始化為1，因為dp[0]是在公式種一切遞推結果的起源，所以dp[0]一定只能是1，如果為0，那么之后的所有的結果都將是0

4、確定遍歷順序：跟我們之前說過的0-1背包問題一樣，nums放在外循環，target在內循環，且內循環倒序

5、最后就是導出dp數組

小尼接下來拉一下解題代碼：

class Solution {public int findTargetSumWays(int[] nums, int target) {int sum = 0;for(int i = 0; i < nums.length; i++) sum += nums[i];if((target + sum) % 2 != 0) return 0;int size = (target + sum) / 2;if(size < 0) size = - size;int[] dp = new int[size + 1];dp[0] = 1;for(int i = 0; i < nums.length; i++){for(int j = size; j >= nums[i]; j--){dp[j] += dp[j - nums[i]];}}return dp[size];} }

小尼簡單的即使一下上述的代碼，其中有一個可以很直接判斷的條件，就是如果（target+sum)%2如果不為0，那么我們直接return false，其實這里如果不為0就是我們題目的條件給不出返回結果是算出的數的背包，其實就是我們不能組成的，然后接下來我們直接就是進行對應對遍歷，我們需要返回可以達到的方法數，最后我們直接返回dp[size]。我們在這道題中先遍歷的是物品，然后再遍歷的是背包的容量，其實就是我們一個個記錄的操作，我們先放入第一個物品，然后我們記錄好dp數組，接下來我們繼續放入之后的物品，然后我們的dp數組根據之前已經疊加了的數據進行對應的繼續增加，最后再返回我們的dp[size]的值

希望上述代碼可以幫助到小伙伴們~~~

總結

以上是生活随笔為你收集整理的My Seventy-first Page - 目标和 - By Nicolas的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。