Chương trình tìm số ngày tối thiểu để ăn N quả cam trong Python

Có n quả cam. Mỗi ngày chọn 1 trong 3 cách: 1) Ăn 1 quả. 2) Nếu n chẵn: ăn n/2 quả. 3) Nếu n chia hết 3: ăn 2*(n/3) quả. Tìm số ngày tối thiểu để ăn hết.

Ví dụ: n = 10, đầu ra = 4 (ngày 1: -1→9, ngày 2: -6→3, ngày 3: -2→1, ngày 4: -1→0).

Giải pháp

DP với memoization đệ quy:

• fun(n):
  • Nếu n trong memo: trả về memo[n]
  • Nếu n ≤ 2: trả về n
  • memo[n] := 1 + min(n%2 + fun(n//2), n%3 + fun(n//3))
  • Trả về memo[n]
• memo := {}, trả về fun(n)

Ý tưởng: n%2 là số ngày ăn 1 quả để n thành chẵn, sau đó ăn n//2. Tương tự cho 3.

Ví dụ minh họa

Xem triển khai sau để hiểu rõ hơn:

def solve(n):
    def fun(n):
        if n in memo:
            return memo[n]
        if n <= 2:
            return n
        memo[n] = 1 + min(n % 2 + fun(n // 2), n % 3 + fun(n // 3))
        return memo[n]
    memo = {}
    return fun(n)

n = 12
print(solve(n))

Đầu vào

12

Đầu ra

4