動的計画法（DP）演習問題

## 動的計画法（DP）とはがわかる参考資料
「習うより慣れろ」の世界らしい。わかるまで何度も繰り返し見ようと思います。
https://qiita.com/drken/items/dc53c683d6de8aeacf5a
https://www.momoyama-usagi.com/entry/info-algo-dp#google_vignette
https://www.youtube.com/watch?v=Y0UEyW64CzM

##  最大部分和問題
### 問題1: 最大部分和問題
**問題文**
整数の配列が与えられたとき、連続する部分配列の要素の和の最大値を求めなさい。
例えば、配列 `[-2, 1, -3, 4, -1, 2, 1, -5, 4]` が与えられた場合、連続する部分配列 `[4, -1, 2, 1]` の和が6で最大となります。
**解法**
この問題は動的計画法の基本問題です。各位置までの最大部分和を記録していくことで解けます。
```c++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxSubArray(vector<int>& nums) {
  // DPテーブル: dp[i]は配列のi番目までの最大部分和
  int n = nums.size();
  int dp = nums[0];      // 現在までの最大部分和
  int result = nums[0];  // 全体の最大部分和

  for (int i = 1; i < n; i++) {
    // 各ステップで「新しく始めるか」「続けるか」の選択を行い、その時点で最も利益の大きい選択をしています。この選択を繰り返すことで、最終的に最大の部分和を持つ部分配列を見つけることができます。
    dp = max(nums[i], dp + nums[i]);
    result = max(result, dp);
  }

  return result;
}

int main() {
  vector<int> nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
  cout << "最大部分和: " << maxSubArray(nums) << endl; // => 最大部分和: 6

  return 0;
}

// このアルゴリズムは以下のステップで動作します：

// 1. 初期化:
// - dp変数を配列の最初の要素で初期化します。これは「現在位置までの最大部分和」を表します。
// - result変数も同様に最初の要素で初期化します。これは「見つかった最大部分和」を記録します。


// 2. イテレーション:
// - 配列の2番目の要素から順に処理します。
// - 各要素iについて、次の選択をします：
//   - その要素から新しい部分配列を始める（nums[i]）
//   - または、前の部分和に現在の要素を追加する（dp + nums[i]）
// - これらの選択肢のうち大きい方を新しいdp値とします。
// - もし新しいdpが現在のresultより大きければ、resultを更新します。

// 3. 結果:
// - 全ての要素を処理した後、resultが最大部分和となります。


// 具体例での動作
// 例として配列 [-2, 1, -3, 4, -1, 2, 1, -5, 4] でのアルゴリズムの動きを追跡します：

// 1. 初期化: dp = -2, result = -2

// 2. i = 1 (値は1):
//   - dp = max(1, -2+1) = max(1, -1) = 1
//   - result = max(-2, 1) = 1

// 3. i = 2 (値は-3):
//   - dp = max(-3, 1+(-3)) = max(-3, -2) = -2
//   - result = max(1, -2) = 1

// 4. i = 3 (値は4):
//   - dp = max(4, -2+4) = max(4, 2) = 4
//   - result = max(1, 4) = 4

// 5. i = 4 (値は-1):
//   - dp = max(-1, 4+(-1)) = max(-1, 3) = 3
//   - result = max(4, 3) = 4

// 6. i = 5 (値は2):
//   - dp = max(2, 3+2) = max(2, 5) = 5
//   - result = max(4, 5) = 5

// 7. i = 6 (値は1):
//   - dp = max(1, 5+1) = max(1, 6) = 6
//   - result = max(5, 6) = 6

// 8. i = 7 (値は-5):
//   - dp = max(-5, 6+(-5)) = max(-5, 1) = 1
//   - result = max(6, 1) = 6

// 9. i = 8 (値は4):
//   - dp = max(4, 1+4) = max(4, 5) = 5
//   - result = max(6, 5) = 6

// 最終的な最大部分和は6となり、これは部分配列[4, -1, 2, 1]の和に対応します。
```

**表で確認**
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3490027/f03e14b6-dc0c-445b-8751-f92646f97310.png)


### 問題2: ナップサック問題
**問題文**
N個のアイテムがあり、各アイテムには価値(value)と重さ(weight)があります。あなたは最大容量Wのナップサックを持っています。ナップサックに入れる品物を選んで、価値の合計が最大になるようにしてください。ただし、各アイテムは1つずつしかありません。

**解法**
典型的なナップサック問題です。2次元のDPテーブルを使って解きます。

```cpp
// 問題2: ナップサック問題
// 問題文
// N個のアイテムがあり、各アイテムには価値(value)と重さ(weight)があります。あなたは最大容量Wのナップサックを持っています。ナップサックに入れる品物を選んで、価値の合計が最大になるようにしてください。ただし、各アイテムは1つずつしかありません。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int knapsack(vector<int>& weights, vector<int>& values, int W) {
  int n = weights.size();

  // 2次元配列（二次元ベクター）を宣言して全ての要素を0で初期化
  // + 1　はベースケース
  // dp[0][w] というベースケース（何も選ばない初期状態）を表現するために、配列のサイズを n+1 に。
  // 容量 0 のケースも考慮するため、配列のサイズは W+1 になります。
  vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

  for (int i = 1; i <= n; i++) {
        for (int w = 0; w <= W; w++) {
            if (weights[i-1] <= w) {
                // アイテムを選ぶか選ばないかの最大値
                dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]);
            } else {
                // アイテムが容量を超える場合は選べない
                dp[i][w] = dp[i-1][w];
            }
        }
    }

    return dp[n][W];
}


int main() {
  vector<int> weights = {2, 3, 4, 5};
  vector<int> values = {3, 4, 5, 6};
  int W = 8;

  cout << "ナップサックの最大価値: " << knapsack(weights, values, W) << endl; // => ナップサックの最大価値: 10

  return 0;
}

// ナップサック問題の基本概念
// ナップサック問題は「限られた容量の中で最大の価値を持つ品物の組み合わせを選ぶ」という最適化問題です。この問題では、各アイテムを「選ぶ」か「選ばない」かの二択があります。

// DPテーブルの構造と意味
// vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
// ここで作成している2次元配列 dp[i][w] の意味は：
// - i: 0からi-1番目までのアイテムだけを考慮した場合
// - w: ナップサックの容量がwの場合
// - dp[i][w]: その条件下での最大価値
// 特に注意すべきは、dp[i][w]のiは実際のアイテムインデックスより1大きくなっています。これはDPテーブルの初期状態（何も選ばない状態）をdp[0][w] = 0として表現するためです。

// アルゴリズムのステップ
// 1. 初期化: dp[0][w] = 0 for all w (アイテムを何も選ばない場合は価値も0)

// 2. DPテーブルの埋め方:
// for (int i = 1; i <= n; i++) {
//     for (int w = 0; w <= W; w++) {
//         if (weights[i-1] <= w) {
//             // アイテムを選ぶか選ばないかの最大値
//             dp[i][w] = max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]);
//         } else {
//             // アイテムが容量を超える場合は選べない
//             dp[i][w] = dp[i-1][w];
//         }
//     }
// }

// この部分で各ステップごとに以下のことを考えています：
// - weights[i-1] <= w: 現在のアイテムが現在の容量に収まる場合
//     - dp[i-1][w]: i-1番目のアイテムまでを考慮し、このアイテム（i-1番目）を「選ばない」場合の最大価値
//     - dp[i-1][w - weights[i-1]] + values[i-1]: i-1番目のアイテムまでを考慮し、このアイテムを「選ぶ」場合の最大価値
//     - これらの大きい方を選びます
// - weights[i-1] > w: 現在のアイテムが容量に収まらない場合
//     - このアイテムは選べないので、前の状態（i-1番目までのアイテムを考慮した最大価値）をそのまま使います

// 3. 最終結果: dp[n][W] が求める答え（全てのアイテムを考慮して容量Wの制限内での最大価値）です

// 具体例での動作
// 例として、以下のデータで考えます：
//  - アイテム: [(重さ2, 価値3), (重さ3, 価値4), (重さ4, 価値5), (重さ5, 価値6)]
//  - ナップサック容量: W = 8

// DP表を埋めていく過程を追ってみましょう：
// 1. 初期状態:
//    - dp[0][w] = 0 for all w (アイテムを何も選ばない場合)
// 2. i=1（最初のアイテム：重さ2, 価値3）の場合:
//    - w < 2: アイテムを入れられない → dp[1][w] = dp[0][w] = 0
//    - w ≥ 2: 選ぶか選ばないかの最大値 → dp[1][w] = max(0, 0 + 3) = 3
// 3. i=2（2番目のアイテム：重さ3, 価値4）の場合:
//    - w < 3: アイテムを入れられない → dp[2][w] = dp[1][w]
//    - w ≥ 3: 選ぶか選ばないかの最大値
//       - 例えば、w=5の場合: dp[2][5] = max(dp[1][5], dp[1][5-3] + 4) = max(3, 3 + 4) = 7
// 4. 以降も同様に計算し、最終的に dp[4][8] を求めます。

// 例として一部のDP表の値を示すと：
//    - dp[1][2] = 3: 最初のアイテムだけで容量2の場合、価値3が最大
//    - dp[2][5] = 7: 最初と2番目のアイテムまでで容量5の場合、価値7が最大（両方選んだ場合）
//    - dp[4][8] = 10: 全てのアイテムを考慮して容量8の場合、価値10が最大
```

**表で確認**
与えられた例:
- アイテム: [(重さ2, 価値3), (重さ3, 価値4), (重さ4, 価値5), (重さ5, 価値6)]
- ナップサック容量: W = 8

DP表の構築過程
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3490027/0a2f0495-5e1f-4413-9e6a-be41a6155d76.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3490027/60a527a7-61cb-4306-a494-3a49c3a7a579.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3490027/baa5cf79-4c0f-417e-b46c-a48796d2add5.png)

**最終結果**
最大価値 = dp[4][8] = 10

### おわりに
数を解いて慣れるためにDPの問題を随時追加していく予定です。

---
株式会社シンシアでは、実務未経験のエンジニアの方や学生エンジニアインターンを採用し一緒に働いています。
※ シンシアにおける働き方の様子はこちら

https://www.wantedly.com/companies/xincere-inc/stories

弊社には年間100人程度の実務未経験の方に応募いただき、技術面接を実施しております。
この記事が少しでも学びになったという方は、ぜひ wantedly のストーリーもご覧いただけるととても嬉しいです！