C#을 사용하여 하향식 접근 방식을 사용하여 최소 단계를 구현하는 방법은 무엇입니까?

MinimumStepstoOneTopdownApproach는 정수 n과 정수 배열을 입력으로 사용합니다. 매개변수 n은 총 요소 수를 포함합니다. 초기 조건은 n이 1인지 여부를 확인합니다. n이 1이면 0을 반환합니다. op1, op2 및 op3을 최대 값으로 초기화합니다. n mod 3이 0이면 MinimumStepstoOneTopdownApproach를 재귀적으로 호출하고 op1에 할당하고, n mod 3이 0이면 MinimumStepstoOneTopdownApproach를 재귀적으로 호출하고 op2에 할당합니다. 그렇지 않으면 n을 1로 빼고 MinimumStepstoOneTopdownApproach를 호출합니다. 마지막으로 Math.Min을 호출하여 세 요소의 최소값을 계산하고 dp 배열에서 값을 반환합니다.

시간 복잡도 - 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