如何使用 C# 使用自下而上的方法实现最小步骤？

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

MinimumStepstoOneBottomdownApproach 以整数 n 作为输入。参数 n 包含元素的总数。初始条件检查 n 是否等于 1。如果 n 等于 1，则返回 0。将 op1、op2 和 op3 初始化为最大值。如果n mod 3 等于0，则递归调用MinimumStepstoOneBottomdownApproach 并将其分配给op1，如果n mod 3 等于0，则递归调用MinimumStepstoOneBottomdownApproach 并将其分配给op2，否则将n 减1 并调用MinimumStepstoOneBottomdownApproach。最后返回 dp 数组中的值

时间复杂度-O(N)

空间复杂度-O(N)

示例

public class DynamicProgramming{
   public int MinimumStepstoOneBottomdownApproach(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 (n % 3 == 0){
            op1 = dp[i / 3];
         }
         if (n % 2 == 0){
            op2 = dp[i / 2];
         }
         op3= dp[i -1];
         dp[i]= Math.Min(Math.Min(op1, op2), op3) + 1;
      }
      return dp[n-1];
   }
}
static void Main(string[] args){
   DynamicProgramming dp = new DynamicProgramming();
   Console.WriteLine(dp.MinimumStepstoOneBottomdownApproach(10))
}