Làm thế nào để thực hiện bước tối thiểu đến một bằng cách sử dụng phương pháp topDown sử dụng C #?

MinimumStepstoOneTopdownApproach lấy số nguyên n và một mảng số nguyên làm đầu vào. Tham số n chứa tổng số phần tử. Điều kiện ban đầu kiểm tra xem n có bằng 1. Nếu n bằng 1 thì trả về 0. Khởi tạo op1, op2 và op3 thành giá trị lớn nhất. Nếu n mod 3 bằng 0 thì gọi đệ quy MinimumStepstoOneTopdownApproach và gán nó cho op1, Nếu n mod 3 bằng 0 thì gọi MinimumStepstoOneTopdownApproach một cách đệ quy và gán nó cho op2 khác trừ n đi 1 và gọi MinimumStepstoOneTopdownApproach. Cuối cùng gọi Math.Min để tính toán tối thiểu ba phần tử và trả về giá trị từ mảng dp

Độ phức tạp về thời gian - O (N)

Độ phức tạp về không gian - O (N)

Ví dụ

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

Đầu ra

3