問題1：最長増加部分列
最長増加部分列（Longest Increasing Subsequence, LIS）問題は、与えられた数列から、要素が厳密に増加する順序で並んでいる最長の部分列を見つける問題です。
class Solution {
public:
int lengthOfLIS(vector<int>& arr) {
// 1. DPテーブルの作成
int size = arr.size();
vector<int> dp(size, 1);
if(size == 1) return 1;
// 2. 初期化（すべての要素が1で初期化済み）
// 3. DPテーブルの更新
int max_length = 0;
for(int i = 1; i < size; ++i)
{
for(int j = 0; j < i; ++j)
{
if(arr[i] > arr[j])
{
dp[i] = max(dp[i], dp[j] + 1);
}
}
max_length = max(max_length, dp[i]);
}
// 4. 結果の返却
return max_length;
}
};問題2：振動数列
振動数列（Wiggle Sequence）問題は、要素が交互に増加と減少を繰り返す最長の部分列を見つける問題です。
class Solution {
public:
int wiggleMaxLength(vector<int>& arr) {
// 1. DPテーブルの作成（up: 上昇で終わる, down: 下降で終わる）
int size = arr.size();
vector<int> up(size, 1), down(size, 1);
// 2. 初期化（すべての要素が1で初期化済み）
// 3. DPテーブルの更新
int max_len = 1;
for(int i = 1; i < size; ++i)
{
for(int j = 0; j < i; ++j)
{
if(arr[i] > arr[j])
{
up[i] = max(up[i], down[j] + 1);
}
else if(arr[j] > arr[i])
{
down[i] = max(down[i], up[j] + 1);
}
}
max_len = max(max_len, max(up[i], down[i]));
}
// 4. 結果の返却
return max_len;
}
};問題3：最長増加部分列の個数
この問題では、最長増加部分列の長さだけでなく、その個数も求める必要があります。
class Solution {
public:
int findNumberOfLIS(vector<int>& arr) {
// 1. DPテーブルの作成（length: 最長増加部分列の長さ, count: 個数）
int size = arr.size();
vector<int> length(size, 1), count(size, 1);
// 2. 初期化（すべての要素が1で初期化済み）
// 3. DPテーブルの更新
for(int i = 1; i < size; ++i)
{
for(int j = 0; j < i; ++j)
{
if(arr[i] > arr[j])
{
if(length[i] == length[j] + 1)
{
count[i] += count[j];
}
else if(length[i] < length[j] + 1)
{
length[i] = length[j] + 1;
count[i] = count[j];
}
}
}
}
// 4. 最長増加部分列の個数を計算
int max_length = 0, result = 0;
for(int i = 0; i < size; ++i)
{
if(length[i] > max_length)
{
max_length = length[i];
result = count[i];
}
else if(length[i] == max_length)
{
result += count[i];
}
}
return result;
}
};問題4：最長数対チェーン
数対チェーン問題は、数対の配列から、各数対の第2要素が次の数対の第1要素より小さくなるように選んだ最長のチェーンを見つける問題です。
class Solution {
public:
int findLongestChain(vector<vector<int>>& pairs) {
// ペアをソート
sort(pairs.begin(), pairs.end());
// 1. DPテーブルの作成
int size = pairs.size();
vector<int> dp(size, 1);
// 2. 初期化（すべての要素が1で初期化済み）
// 3. DPテーブルの更新
int max_chain = 1;
for(int i = 1; i < size; ++i)
{
for(int j = 0; j < i; ++j)
{
if(pairs[j][1] < pairs[i][0])
{
dp[i] = max(dp[i], dp[j] + 1);
}
}
max_chain = max(max_chain, dp[i]);
}
// 4. 結果の返却
return max_chain;
}
};問題5：最長定差部分列
この問題では、与えられた差分を持つ最長の等差部分列を見つけます。
// 最初の解法（時間制限を超える可能性があるが理解しやすい）
// class Solution {
// public:
// int longestSubsequence(vector<int>& arr, int diff) {
// // 1. DPテーブルの作成
// int size = arr.size();
// vector<int> dp(size, 1);
// // 2. 初期化（すべての要素が1で初期化済み）
// // 3. DPテーブルの更新
// int max_len = 1;
// for(int i = 1; i < size; ++i)
// {
// for(int j = i - 1; j >= 0; --j)
// {
// if(arr[i] - arr[j] == diff)
// {
// dp[i] = max(dp[i], dp[j] + 1);
// break;
// }
// }
// max_len = max(max_len, dp[i]);
// }
// // 4. 結果の返却
// return max_len;
// }
// };
// 最適化された解法（ハッシュテーブルを使用）
class Solution {
public:
int longestSubsequence(vector<int>& arr, int diff) {
// 1. ハッシュテーブルの作成（値をキー、最長部分列の長さを値とする）
unordered_map<int, int> dp_map;
// 2. 初期化
dp_map[arr[0]] = 1;
// 3. ハッシュテーブルの更新
int max_len = 1;
for(int i = 1; i < arr.size(); ++i)
{
int prev = arr[i] - diff;
if(dp_map.find(prev) != dp_map.end())
{
dp_map[arr[i]] = dp_map[prev] + 1;
}
else
{
dp_map[arr[i]] = 1;
}
max_len = max(max_len, dp_map[arr[i]]);
}
// 4. 結果の返却
return max_len;
}
};問題6：最長フィボナッチ部分列の長さ
フィボナッチ部分列は、すべてのiに対してseq[i] + seq[i+1] = seq[i+2]が成り立つ部分列です。
class Solution {
public:
int lenLongestFibSubseq(vector<int>& arr) {
// この問題では2次元のDPテーブルが必要
// dp[i][j]は最後の2要素がiとjである最長のフィボナッチ部分列の長さを表す
// 1. DPテーブルの作成
int size = arr.size();
vector<vector<int>> dp(size, vector<int>(size, 2));
// 要素とそのインデックスを関連付けるハッシュテーブル
unordered_map<int, int> value_to_index;
for(int i = 0; i < size; ++i)
{
value_to_index[arr[i]] = i;
}
// 2. 初期化（すべての要素が2で初期化済み）
// 3. DPテーブルの更新
int max_length = 2;
for(int j = 2; j < size; j++)
{
for(int i = 1; i < j; i++)
{
int prev_val = arr[j] - arr[i];
if(prev_val < arr[i] && value_to_index.count(prev_val))
{
int k = value_to_index[prev_val];
dp[i][j] = dp[k][i] + 1;
max_length = max(max_length, dp[i][j]);
}
}
}
// 4. 結果の返却
return max_length < 3 ? 0 : max_length;
}
};問題7：最長等差数列
等差数列は、連続する要素の差が一定である数列です。この問題では、与えられた配列から最長の等差数列部分列を見つけます。
class Solution {
public:
int longestArithSeqLength(vector<int>& arr) {
// 1. DPテーブルとハッシュテーブルの作成
int size = arr.size();
unordered_map<int, int> value_to_index;
vector<vector<int>> dp(size, vector<int>(size, 2));
// 2. 初期化
value_to_index[arr[0]] = 0; // 最初の値を保存
// 3. DPテーブルの更新
int max_length = 2;
for(int i = 1; i < size; ++i) // 2番目から最後までの要素を固定
{
for(int j = i + 1; j < size; ++j) // iの後ろの要素を探索
{
int prev_val = 2 * arr[i] - arr[j]; // 等差数列の前の値を計算
if(value_to_index.count(prev_val))
{
int k = value_to_index[prev_val];
dp[i][j] = dp[k][i] + 1;
}
max_length = max(max_length, dp[i][j]);
}
value_to_index[arr[i]] = i; // 現在の要素のインデックスを更新
}
// 4. 結果の返却
return max_length;
}
};問題8：等差数列の分割
この問題では、配列内のすべての等差数列部分列の個数を数えます。
class Solution {
public:
int numberOfArithmeticSlices(vector<int>& arr) {
// 1. DPテーブルとハッシュテーブルの作成
int size = arr.size();
vector<vector<int>> dp(size, vector<int>(size, 0));
unordered_map<long long, vector<int>> value_to_indices;
for(int i = 0; i < size; ++i)
{
value_to_indices[arr[i]].push_back(i); // 同じ値を持つ複数のインデックスを記録
}
// 2. 初期化（すべての要素が0で初期化済み）
// 3. DPテーブルの更新
int total_count = 0;
for(int j = 2; j < size; ++j) // 3番目から最後までの要素を固定
{
for(int i = 1; i < j; ++i) // 2番目からj-1までの要素を探索
{
long long prev_val = (long long)2 * arr[i] - arr[j]; // 等差数列の前の値を計算
if(value_to_indices.count(prev_val)) // 複数のprev_valが存在する可能性がある
{
for(int k : value_to_indices[prev_val]) // すべてのprev_valに対して処理
{
if(k < i) // kがiとjの前にある場合のみ有効
{
dp[i][j] += dp[k][i] + 1;
}
}
}
total_count += dp[i][j];
}
}
// 4. 結果の返却
return total_count;
}
};