動的計画法（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で最大となります。
解法
この問題は動的計画法の基本問題です。各位置までの最大部分和を記録していくことで解けます。
#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]の和に対応します。
表で確認
問題2: ナップサック問題
問題文
N個のアイテムがあり、各アイテムには価値(value)と重さ(weight)があります。あなたは最大容量Wのナップサックを持っています。ナップサックに入れる品物を選んで、価値の合計が最大になるようにしてください。ただし、各アイテムは1つずつしかありません。
解法
典型的なナップサック問題です。2次元のDPテーブルを使って解きます。
// 問題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表の構築過程
最終結果
最大価値 = dp[4][8] = 10
おわりに
数を解いて慣れるためにDPの問題を随時追加していく予定です。
株式会社シンシアでは、実務未経験のエンジニアの方や学生エンジニアインターンを採用し一緒に働いています。
※ シンシアにおける働き方の様子はこちら
弊社には年間100人程度の実務未経験の方に応募いただき、技術面接を実施しております。
この記事が少しでも学びになったという方は、ぜひ wantedly のストーリーもご覧いただけるととても嬉しいです！