如何使用 C# 使用 topDown 方法实现最小步进？

Z时代
2024-01-10
分类：综合

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));
}