Cách tìm số bước tối thiểu để giảm về 1 bằng phương pháp Top-Down trong C#

Phương pháp MinimumStepstoOneTopdownApproach nhận n và mảng dp. Nếu n == 1 trả về 0. Khởi tạo op1, op2, op3 = int.MaxValue. Nếu n % 3 == 0 gọi đệ quy n/3 gán cho op1; nếu n % 2 == 0 gọi đệ quy n/2 gán cho op2; op3 gọi đệ quy n-1. Trả về min của ba giá trị + 1 và lưu vào dp[n].

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

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

Ví dụ

public class DynamicProgramming
{
    public int MinimumStepstoOneTopdownApproach(int n, int[] dp)
    {
        if (n == 1)
        {
            return 0;
        }
        int 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)); // Output: 3
}

Kết quả đầu ra

3