【競プロ-AtCoder】【動的計画法(DP)】A18 Subset Sum【Golang】【初学者】

# **A18 Subset Sum**

問題リンク：https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_r

解法：DP + bit全探索

備考：二次元のDP（部分和問題）

- bit全探索とは
    
    bit全探索を使用する状況は、「使う/使わない」「取る/取らない」「買う/買わない」「参加する/参加しない」などの二択を選ぶとき。
    
    例えば、物を買う買わないについては、「i桁目が0ならi番目のものは買わない」「i桁目が1ならi番目のものを買う」のような感じ。

</br>

---

- 鉄則本をもとにした回答


    ### **1. 入力の受け取り**
    
    ```go
    var N, S int
    fmt.Scan(&N, &S)
    ```
    
    - `N` は数列 A の要素数。
    - `S` は目標とする合計値。
    - ユーザーが標準入力で N と S を与えます。
    
    ```go
    A := make([]int, N+1)
    for i := 1; i <= N; i++ {
    	fmt.Scan(&A[i])
    }
    ```
    
    数列A を受け取ります。配列は 1-indexed で扱われ、A[0]は使いません。
    
    ---
    
    ### **2. DP 配列の初期化**
    
    ```go
    dp := make([][]bool, N+1)
    for i := range dp {
    	dp[i] = make([]bool, S+1)
    }
    ```
    
    - `dp[i][j]` は、**数列の先頭から i 番目までの要素を使って、合計が j となる部分和を作れるかどうか**を表します。
        - `true` なら可能、`false` なら不可能。
    - 配列のサイズは (N+1)×(S+1)。0 から N 番目の要素、0 から S までの合計を考慮します。
    
    ---
    
    ### **3. DP 配列の初期条件**
    
    ```go
    dp[0][0] = true
    for i := 1; i <= S; i++ {
    	dp[0][i] = false
    }
    ```
    
    - 初期条件：
        - **要素を一つも使わない場合（i = 0）で、合計が 0 になることは可能**なので、`dp[0][0] = true`。
        - 要素を使わずに正の値 j>0 を作ることは不可能なので、`dp[0][j] = false`（j≥1）。
    
    ---
    
    ### **4. DP 配列の遷移式**
    
    ```go
    for i := 1; i <= N; i++ {
    	for j := 0; j <= S; j++ {
    		if j < A[i] {
    			if dp[i-1][j] {
    				dp[i][j] = true
    			} else {
    				dp[i][j] = false
    			}
    		}
    		if j >= A[i] {
    			if dp[i-1][j] || dp[i-1][j-A[i]] {
    				dp[i][j] = true
    			} else {
    				dp[i][j] = false
    			}
    		}
    	}
    }
    ```
    
    - 外側のループ：現在考慮する要素の範囲を広げる（1 番目から N 番目まで）。
    - 内側のループ：合計値 j を 0 から S までチェック。
    
    **遷移の条件：**
    
    1. **j < A[i]j：**
        - 現在の要素 A[i] を使うと j を超えてしまうため、**A[i]を使わない場合だけを考慮**します。
        - dp[i][j] = dp[i−1][j]。
    2. **j ≥ A[i]j：**
        - 現在の要素 A[i] を使う場合と使わない場合の両方を考慮します。
        - dp[i][j] = dp[i−1][j] || dp[i−1][j−A[i]]。
            - `dp[i-1][j]`：A[i] を使わない場合、合計が j にできるなら true。
            - `dp[i-1][j-A[i]]`：A[i] を使う場合、残りの合計 j−A[i] が可能なら true。
    - 視覚的な解説
        
        数列A = [2, 3, 7], 目標の合計S = 10 の場合を考える。
        
        DP配列の意味
        
        - dp[i][j]は、数列の最初からi番目までの要素を使って、合計がjとなる部分和を作れるかを示す。
        
        DP配列は以下のような二次元テーブルで表される：
        
        | i/j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
        | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
        | i = 0 | true | false | false | false | false | false | false | false | false | false | false |
        | i = 1 | ? | ? | ? | ? | ? | ? | ? | ? | ? | ? | ? |
        | i = 2 | ? | ? | ? | ? | ? | ? | ? | ? | ? | ? | ? |
        | i = 3 | ? | ? | ? | ? | ? | ? | ? | ? | ? | ? | ? |
        
        行(i)：数列のどこまで考えるか
        
        列(j)：目標の部分和の値
        
        ---
        
        ### 遷移の考え方
        
        **基本的なアイデア**
        
        「数列の要素A[i]を使うか、使わないか」の2つの選択を考える。
        
        1. A[i]を使わない場合：
            - jを作るために、前の状態dp[i-1][j]が可能なら、そのままdp[i][j] = true となる。
        2. A[j]を使う場合：
            - A[i]を選ぶことで、合計jを作りたい。
            - この場合、残りの合計 j - A[i] が作れるならdp[i][j] = true となる。つまり、dp[i-1][j-A[i]がtrueとなる。
        
        ---
        
        ### 可視化して遷移を確認
        
        ステップ1：異初期条件 i = 0
        
        - i = 0 は、「どの要素も使わない場合」を意味する。
        - 合計 j = 0 のみ true、他はfalse。
        
        ---
        
        ステップ2：i = 1, A[1] = 2
        
        - A[1] = 2 を使う場合、j -2 を作れるなら j を作れる
        - 更新：
            - dp[1][2] = true (2を作れる)
            - 他はdp[1][j] = dp[0][j]のまま
        
        | i/j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
        | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
        | i = 0 | true | false | false | false | false | false | false | false | false | false | false |
        | i = 1 | true | false | true | false | false | false | false | false | false | false | false |
        
        ---
        
        ステップ3：i = 2, A[2] = 3
        
        - A[2] = 3 を使う場合：
            - dp[2][3] = true（3を作れる）
            - dp[2][5] = true （2 + 3 = 5 を作れる）
        - 他は前の状態を引き継ぐ
        
        | i/j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
        | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
        | i = 0 | true | false | false | false | false | false | false | false | false | false | false |
        | i = 1 | true | false | true | false | false | false | false | false | false | false | false |
        | i = 2 | true | false | true | true | false | true | false | false | false | false | false |
        
        ---
        
        ステップ4：i = 3, A[3] = 7
        
        - A[3] = 7 を使う場合：
            - dp[3][7] = true（7を作れる）
            - dp[3][9] = true（2 + 7 = 9を作れる）
            - dp[3][10] = true（3 + 7 = 10を作れる）
        
        | i/j | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
        | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
        | i = 0 | true | false | false | false | false | false | false | false | false | false | false |
        | i = 1 | true | false | true | false | false | false | false | false | false | false | false |
        | i = 2 | true | false | true | true | false | true | false | false | false | false | false |
        | i = 3 | true | false | true | true | false | true | false | true | false | true | true |
        
        ### 結果
        
        - 最終的にdp[N][S] = dp[3][10] = true なので、合計S = 10 を作れる
        - 答えはYes
        
        ### ポイントまとめ
        
        1. 各ステップでdp[i][j]を更新する際、A[i]を使う場合と使わない場合の両方を考慮。
        2. A[i]を使う場合、「残りの合計」が作れるかどうかを過去の状態から参照する。
        3. DPテーブルを埋めていくことで、部分和問題の解答を効率よく得られる。