C#でトップダウンアプローチにより「1への最小ステップ数」を実装する方法

概要

「1への最小ステップ数（Minimum Steps to One）」は、動的計画法の代表的な問題の一つです。整数 n を以下の操作を繰り返して 1 に到達させる際、必要な最小の操作回数を求めます。

• n が 3 で割り切れる場合：n を n / 3 にする
• n が 2 で割り切れる場合：n を n / 2 にする
• 常に可能：n から 1 を引く（n - 1 にする）

本記事では、C# を用いてトップダウン方式（メモ化再帰）でこの問題を実装する方法を解説します。

アルゴリズムの手順

MinimumStepstoOneTopdownApproach メソッドは、整数 n とメモ化用の整数配列 dp を引数として受け取ります。処理の流れは以下の通りです。

1. 初期条件のチェック： n が 1 の場合は操作不要のため 0 を返します。
2. 変数の初期化： 3つの選択肢の結果を格納する op1、op2、op3 をそれぞれ int.MaxValue（最大値）で初期化します。
3. 3で割る操作： n % 3 == 0 の場合、n / 3 を引数に再帰呼び出しを行い、結果を op1 に代入します。
4. 2で割る操作： n % 2 == 0 の場合、n / 2 を引数に再帰呼び出しを行い、結果を op2 に代入します。
5. 1を引く操作： n - 1 を引数に再帰呼び出しを行い、結果を op3 に代入します。
6. 最小値の算出と記録： Math.Min を使って3つの選択肢の中の最小値に +1 した値を計算し、その結果を dp 配列に保存して返します。

dp 配列に結果を保存することで、同じ n に対する再計算を回避でき、指数時間だった素朴な再帰を O(N) にまで高速化できます。

計算量

• 時間計算量： O(N)
• 空間計算量： O(N)（再帰スタックおよびメモ化配列分）

実装例

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

static void Main(string[] args){
   DynamicProgramming dp = new DynamicProgramming();
   int[] dpArr = new int[150];
   Console.WriteLine(dp.MinimumStepstoOneTopdownApproach(10, dpArr));
}

実行結果

3

入力 n = 10 の場合の出力は 3 となります。これは「10 → 9（1を引く）→ 3（3で割る）→ 1（3で割る）」という 3 回の操作が最短経路であることを示しています。