LeetCode(494):ターゲットおよびTargetSum(Java)

2019.10.24#プログラマー筆記試験必須#LeetCodeゼロブラシ個人メモ整理(継続更新)
github:https://github.com/ChopinXBP/LeetCode-Babel
この問題は表面的には再帰問題であり,幸い再帰層数も特に多くなく,各層分岐も爆発的ではないので,直接再帰もタイムアウトしない.しかし、この問題にはもっと巧妙な方法があり、01リュックサックの問題に変換することができます.
データNをABの2つの部分と見なして、A記号はすべて正を取って、B記号はすべて負を取って、あります

sumA - sumB = S

等式変換には

2 * sumA = S + sumA + sumB = S + sumN = target ( target = S + sumN)

だから配列の中で1つの集合Aを見つけて満たす限り

sumA = target / 2

すなわち実行可能な解である.問題:
動的計画配列dpが作成され、dp[i]は構成およびiの集合の数を表し、したがってdp[0]=1は空の集合が存在する.状態遷移方程式は次のとおりです.

dp[i] += dp[i - num]; (i >= num)

トランスポートゲート:ターゲットとターゲットと
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.
非負の整数配列,a 1,a 2,...,an,およびターゲット数,Sが与えられる.2つの記号+と-があります.配列内の任意の整数について、+または-から記号を選択して前に追加できます.
最終配列と目標数Sのすべてのシンボルを追加できるメソッド数を返します.

   1:
  : nums: [1, 1, 1, 1, 1], S: 3
  : 5
  : 
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
   5          3。

  :
    ，       20。
           1000。
           32     。

/**
 *
 * 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.
 *           ，a1, a2, ..., an,       ，S。         +   -。            ，      +   -            。
 *                S            。
 *
 */

public class TargetSum {
    //  
    public int findTargetSumWays(int[] nums, int S) {
        result = 0;
        Solution(nums, 0, 0, S);
        return result;
    }

    private int result;
    public void Solution(int[] nums, int idx, int curNum, int sum){
        if(idx == nums.length){
            result = curNum == sum ? result + 1 : result;
            return;
        }
        Solution(nums, idx + 1, curNum + nums[idx], sum);
        Solution(nums, idx + 1, curNum - nums[idx], sum);
    }

    //    ：01  
    //   N  AB    ，A     ，B     ， sumA-sumB = S
    //     2sumA = S+sumA+sumB = S+sumN = target
    //          A  sumA=target/2，       。
    public int findTargetSumWays2(int[] nums, int S) {
        int sumN = 0;
        for(int num : nums){
            sumN += num;
        }
        //        S ，  target         
        if(sumN < S || ((sumN + S) & 1) == 1){
            return 0;
        }

        //dp[i]      i      ，    dp[0] = 1;
        int target = (sumN + S) >> 1;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for(int num : nums){
            for(int i = target; i >= num; i--){
                dp[i] += dp[i - num];
            }
        }
        return dp[target];
    }
}

#Coding 1時間、Copying 1秒.いいねを残してくれてありがとう