C#のボトムアップ方式で「1にする最小ステップ数」を実装する方法

問題の概要：「1にする最小ステップ数」とは

「1への最小ステップ数（Minimum Steps to One）」は、動的計画法（DP）の入門問題としてよく知られています。整数 n が与えられ、次の3種類の操作を繰り返し適用して、n を 1 に到達させるまでの最小回数を求めます。

• 操作1： n が 3 で割り切れるとき、n を 3 で割る
• 操作2： n が 2 で割り切れるとき、n を 2 で割る
• 操作3： 常に実行可能。n から 1 を引く

ボトムアップ方式（Tabulation）の考え方

ボトムアップ方式では、再帰呼び出しを行わずに、小さな部分問題から順番に答えを計算し、dp 配列に結果を保存していきます。dp[i] は「i を 1 にするために必要な最小ステップ数」を表します。

アルゴリズムの手順

1. 整数 n を入力として受け取ります。
2. 初期条件として、n が 1 の場合は 0 を返します。
3. 候補値 op1・op2・op3 を最大値（int.MaxValue）で初期化します。
4. i が 3 で割り切れる場合は、op1 に dp[i / 3] を代入します。
5. i が 2 で割り切れる場合は、op2 に dp[i / 2] を代入します。
6. op3 には常に dp[i - 1] を代入します。
7. dp[i] = min(op1, op2, op3) + 1 として最小ステップ数を記録します。
8. すべての計算が終わったら、dp 配列から最終的な値を返します。

C#での実装例

public class DynamicProgramming{
    public int MinimumStepstoOne(int n){
        int[] dp = new int[100];
        dp[1] = 0;
        for (int i = 2; i <= n; i++){
            int op1 = int.MaxValue, op2 = int.MaxValue, op3 = int.MaxValue;
            if (i % 3 == 0){
                op1 = dp[i / 3];
            }
            if (i % 2 == 0){
                op2 = dp[i / 2];
            }
            op3 = dp[i - 1];
            dp[i] = Math.Min(Math.Min(op1, op2), op3) + 1;
        }
        return dp[n];
    }
}

static void Main(string[] args){
    DynamicProgramming dp = new DynamicProgramming();
    Console.WriteLine(dp.MinimumStepstoOne(10));
}

実行結果

3

なぜ「n = 10 で 3 ステップ」になるのか

n = 10 の場合、最短経路は次のようになります。

10 → 9（−1）→ 3（÷3）→ 1（÷3）

このように、単純に 1 を引き続けるだけでは 4 ステップ以上かかるところを、割り算をうまく組み合わせることで 3 ステップに短縮できます。これこそが動的計画法による最適化のポイントです。

計算量

時間計算量： O(N) ― 各 i に対して定数回の比較と配列参照しか行わないためです。

空間計算量： O(N) ― 中間結果を保存するための dp 配列が必要になるためです。