動的プログラミング基礎問題集 =======

問題1: スキー場の最長滑走ルート

難易度: 入門～中級
解法: メモ化探索

スキー場の地図が与えられ、各地点の標高がわかっています。標高が高い地点から低い地点へのみ滑ることができるとき、最長の滑走ルートの長さを求めてください。

解法として、すべての地点を起点としてDFS（深さ優先探索）を行い、メモ化テクニックを用いて計算結果を保存します。これにより、同じ地点が再び探索されるのを防ぎ、計算量を大幅に削減できます。

コード例:

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

const int MAX = 110;
int rows, cols;
int max_altitude = 0;
int max_x, max_y;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
vector altitude(MAX, vector<int>(MAX));
vector dp(MAX, vector<int>(MAX));
int result = 0;

int dfs(int x, int y) {
    if (dp[x][y] != 0) return dp[x][y];
    
    int longest = 0;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 1 && nx <= rows && ny >= 1 && ny <= cols && 
            altitude[nx][ny] < altitude[x][y]) {
            longest = max(longest, dfs(nx, ny));
        }
    }
    
    dp[x][y] = longest + 1;
    return dp[x][y];
}

int main() {
    cin >> rows >> cols;
    
    // Initialize altitude with a large value
    for (int i = 0; i < MAX; i++) {
        fill(altitude[i].begin(), altitude[i].end(), INT_MAX);
    }
    
    // Read input and find the highest point
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            cin >> altitude[i][j];
            if (altitude[i][j] > max_altitude) {
                max_x = i;
                max_y = j;
                max_altitude = altitude[i][j];
            }
        }
    }
    
    // Calculate the longest path from each point
    for (int i = 1; i <= rows; i++) {
        for (int j = 1; j <= cols; j++) {
            result = max(result, dfs(i, j));
        }
    }
    
    cout << result << endl;
    return 0;
}

問題2: 最長減少部分列

難易度: 入門～中級
解法: 動的プログラミング

数列が与えられたとき、最長の減少部分列（左から右へ見て値が単調に減少する部分列）の長さを求めてください。

解法として、dp[i]をi番目の要素を含む最長減少部分列の長さと定義します。状態遷移方程式はdp[j] = max(dp[j], dp[i] + 1) (1 ≤ i < j, a[i] > a[j])となります。

コード例:

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

int main() {
    int n;
    cin >> n;
    
    vector<int> sequence(n + 1);
    vector<int> dp(n + 1, 1); // Initialize with 1 (each element is a subsequence of length 1)
    int max_length = 1;
    
    for (int i = 1; i <= n; i++) {
        cin >> sequence[i];
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (sequence[j] > sequence[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
        max_length = max(max_length, dp[i]);
    }
    
    cout << max_length << endl;
    return 0;
}

問題3: 紙の伝達

難易度: 入門
解法: 動的プログラミング

グリッド上のある地点から別の地点へ紙を伝達します。各地点には「八卦値」という値があり、移動するたびにその値が累積されます。左上から右下へ移動する際に累積される八卦値の合計を最小にする経路を求めてください。

解法として、dp[i][j]を(i,j)地点に到達するまでの最小八卦値の合計と定義します。状態遷移方程式はdp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]となります。

コード例:

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

const int MAX = 2200;
int n, m;
vector grid(MAX, vector<int>(MAX));
vector dp(MAX, vector<int>(MAX));

int main() {
    cin >> n >> m;
    
    // Read grid values
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> grid[i][j];
        }
    }
    
    // Initialize dp with a large value
    for (int i = 0; i < MAX; i++) {
        fill(dp[i].begin(), dp[i].end(), INT_MAX);
    }
    
    // Starting point
    dp[1][1] = grid[1][1];
    
    // Fill dp table
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i > 1) {
                dp[i][j] = min(dp[i][j], dp[i-1][j] + grid[i][j]);
            }
            if (j > 1) {
                dp[i][j] = min(dp[i][j], dp[i][j-1] + grid[i][j]);
            }
        }
    }
    
    cout << dp[n][m] << endl;
    return 0;
}

問題4: 数字の三角形

難易度: 高級
解法: メモ化探索

頂点から始まる数字の三角形が与えられています。各ステップで、現在の数字の下にある左右どちらかの数字に移動できます。頂点から底辺まで移動する際の数字の合計値を最大化する経路を求めてください。

解法として、頂点から下に向かってDFSを行い、各地点での最大合計値をメモ化します。これにより、O(2^n)の計算量をO(n^2)に削減できます。

コード例:

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

const int MAX = 2200;
int n;
vector triangle(MAX, vector<int>(MAX));
vector dp(MAX, vector<int>(MAX));

int dfs(int depth, int pos) {
    if (depth > n || pos > depth) return 0;
    if (dp[depth][pos] != 0) return dp[depth][pos];
    
    int left_path = dfs(depth + 1, pos);
    int right_path = dfs(depth + 1, pos + 1);
    
    dp[depth][pos] = max(left_path, right_path) + triangle[depth][pos];
    return dp[depth][pos];
}

int main() {
    cin >> n;
    
    // Read triangle values
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> triangle[i][j];
        }
    }
    
    cout << dfs(1, 1) << endl;
    return 0;
}

問題5: 再帰関数の最適化

難易度: 入門～中級
解法: メモ化

再帰的に定義された関数の値を効率的に計算する問題です。与えられた再帰式をそのまま実装すると計算量が爆発的に増加するため、メモ化テクニックを用いて計算結果を保存し、重複計算を避けます。

解法として、再帰式をそのまま実装し、引数の組み合わせに対する計算結果をメモ化テーブルに保存します。これにより、同じ引数での再帰呼び出しを避け、計算量を大幅に削減できます。

コード例:

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

int a, b, c;
vector> dp(60, vector(60, vector<int>(60)));

int recursive_func(int x, int y, int z) {
    if (x <= 0 || y <= 0 || z <= 0) {
        return 1;
    }
    
    if (dp[x][y][z] != 0) {
        return dp[x][y][z];
    }
    
    if (x > 20 || y > 20 || z > 20) {
        return dp[x][y][z] = recursive_func(20, 20, 20);
    }
    
    if (x < y && y < z) {
        return dp[x][y][z] = recursive_func(x, y, z-1) + 
                             recursive_func(x, y-1, z-1) - 
                             recursive_func(x, y-1, z);
    }
    
    return dp[x][y][z] = recursive_func(x-1, y, z) + 
                         recursive_func(x-1, y-1, z) + 
                         recursive_func(x-1, y, z-1) - 
                         recursive_func(x-1, y-1, z-1);
}

int main() {
    while (true) {
        cin >> a >> b >> c;
        if (a == -1 && b == -1 && c == -1) {
            break;
        }
        
        int result;
        if (a <= 0 || b <= 0 || c <= 0) {
            result = 1;
        } else {
            result = recursive_func(a, b, c);
        }
        
        cout << "w(" << a << ", " << b << ", " << c << ") = " << result << endl;
    }
    return 0;
}