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

Phương pháp MinimumStepstoOneBottomdownApproach nhận số nguyên n. Điều kiện ban đầu: nếu n == 1 trả về 0. Khởi tạo op1, op2, op3 = giá trị lớn nhất. Nếu n % 3 == 0 gán dp[i/3] cho op1; nếu n % 2 == 0 gán dp[i/2] cho op2; op3 = dp[i-1]. Cuối cùng trả về giá trị từ mảng dp.

Độ 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 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 (i % 3 == 0)
            {
                op1 = dp[i / 3];
            }
            if (i % 2 == 0)
            {
                op2 = dp[i / 2];
            }
            op3 = dp[i - 1];
            dp[i] = Math.Min(Math.Min(op1, op2), op3) + 1;
        }
        return dp[n];
    }
}

static void Main(string[] args)
{
    DynamicProgramming dp = new DynamicProgramming();
    Console.WriteLine(dp.MinimumStepstoOneBottomdownApproach(10)); // Output: 3
}

Kết quả đầu ra

3

Lưu ý: Code gốc có lỗi logic (sử dụng n thay vì i trong điều kiện modulo). Phiên bản trên đã sửa để đúng thuật toán Bottom-Up.