1. 計算量評価の基本モデル

動的計画法（DP）の計算量を正確に見積もるためには、アルゴリズムを以下の3つの要素に分解して考えます。

• 状態（State）： dp[i] や dp[i][j] と定義される、部分問題の解を保持する変数。
• 状態の総数： 計算が必要なすべての部分問題の数（1次元DPなら $n$、2次元DPなら $n \times m$ など）。
• 遷移コスト： 1つの状態（例：dp[i]）の値を決定するために必要な計算ステップ。通常は $O(1)$ ですが、ループを伴う場合は $O(k)$ となることがあります。

2. 時間計算量の算出

基本的な計算式は以下の通りです。

時間計算量 = 状態の総数 × 1つの状態あたりの遷移コスト

ケース1：1次元DP（例：階段の上り方）

$n$ 段の階段を1段または2段ずつ登る方法の総数を求める問題です。

int countWays(int n) {
    if (n <= 1) return 1;
    std::vector<int> memo(n + 1);
    memo[0] = 1; 
    memo[1] = 1;
    for (int i = 2; i <= n; i++) {
        // 遷移式：前の2つの状態を加算
        memo[i] = memo[i - 1] + memo[i - 2]; // 遷移コストはO(1)
    }
    return memo[n];
}

• 状態の数： memo[0] から memo[n] までの $n$ 個。
• 遷移コスト： 1回の加算のみなので $O(1)$。
• 時間計算量： $O(n) \times O(1) = O(n)$。

ケース2：2次元DP（例：格子状経路の最小コスト）

グリッドの左上から右下まで移動する際の最小コストを計算します。

int findMinPath(std::vector<std::vector<int>>& field) {
    int rows = field.size();
    int cols = field[0].size();
    auto table = field; // DPテーブルの初期化

    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (r == 0 && c == 0) continue;
            int top = (r > 0) ? table[r - 1][c] : INT_MAX;
            int left = (c > 0) ? table[r][c - 1] : INT_MAX;
            table[r][c] += std::min(top, left); // 遷移コストはO(1)
        }
    }
    return table[rows - 1][cols - 1];
}

• 状態の数： $rows \times cols$ の全マス分。
• 遷移コスト： min 比較と加算のみなので $O(1)$。
• 時間計算量： $O(rows \times cols)$。

ケース3：遷移コストが $O(n)$ になる場合（例：最長増加部分列）

各状態を決めるために、それ以前のすべての状態を確認する必要があるケースです。

int lengthOfLIS(std::vector<int>& nums) {
    int n = nums.size();
    std::vector<int> dp(n, 1);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = std::max(dp[i], dp[j] + 1); // 遷移コストがループに依存
            }
        }
    }
    return *max_element(dp.begin(), dp.end());
}

• 状態の数： $n$。
• 遷移コスト： 各 $i$ に対して $0$ から $i-1$ までのループが発生するため、平均 $O(n)$。
• 時間計算量： $O(n) \times O(n) = O(n^2)$。

3. 空間計算量の算出と最適化

空間計算量は、アルゴリズムが実行のために確保する「追加のメモリ領域」に基づきます。一般的には、用意したDPテーブルのサイズがそのまま空間計算量となります。

メモリ節約技術：ローリング配列（次元圧縮）

遷移式が「直前の行」や「直前の数要素」のみに依存する場合、古い情報を捨てることで空間計算量を削減できます。

例：階段問題（1次元 → 定数）

int optimizedWays(int n) {
    int prev = 1, curr = 1;
    for (int i = 2; i <= n; i++) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

• 最適化前： $O(n)$（配列を使用）。
• 最適化後： $O(1)$（変数のみ）。

例：ナップサック問題（2次元 → 1次元）

2次元配列 dp[アイテム数][容量] を dp[容量] のみに圧縮することで、空間計算量を $O(N \times W)$ から $O(W)$ に削減可能です。

4. まとめ表

計算量を見積もる際は、単にループの回数を数えるのではなく、「いくつの状態を定義し、それぞれを埋めるのにどれだけの労力がかかるか」という視点を持つことが重要です。また、空間の最適化を行っても、計算すべき状態の総数は変わらないため、時間計算量は基本的に減少しない点に注意してください。