Tất cả thử thách
Trung bình 1 đã giải Tỷ lệ chấp nhận 100.0%

Trừ Các Chữ Số Để Đạt Đến Số 0

Sử dụng ít phép trừ chữ số nhất có thể để đạt đến số 0.

Bạn sẽ học được gì

  • Mô hình hóa quá trình thành trạng thái và bước đi
  • Tính số bước ít nhất về 0
  • So sánh QHĐ với lối tắt tham lam

Đề bài

Xem bản gốc (English)

Ở mỗi bước, chọn một chữ số thập phân khác 0 hiện đang có trong số và trừ chữ số đó. Các chữ số được lấy từ giá trị mới sau mỗi bước. Hãy tìm số bước tối thiểu cần thiết để đạt đến số 0.

Cài đặt hàm removing_digits(n).

Đầu vào

n: Số nguyên dương ban đầu.

Đầu ra

Trả về số bước trừ ít nhất.

Ràng buộc

1 ≤ n ≤ 1.000.000. Không được phép trừ số 0 vì không có ý nghĩa.

Ví dụ

Ví dụ 1
Đầu vào:
n = 14

Kết quả mong đợi:
expected = 3
Đầu vào:
long long n = 14;

Kết quả mong đợi:
long long expected = 3;
Đầu vào:
long n = 14;

Kết quả mong đợi:
long expected = 3;

Giải thích

14 → 10 → 9 → 0 sử dụng ba bước. Không có phép trừ đầu tiên nào có thể đạt đến 0 chỉ trong hai bước.

Ví dụ 2
Đầu vào:
n = 7

Kết quả mong đợi:
expected = 1
Đầu vào:
long long n = 7;

Kết quả mong đợi:
long long expected = 1;
Đầu vào:
long n = 7;

Kết quả mong đợi:
long expected = 1;

Giải thích

Trừ chữ số duy nhất là 7 để đạt 0 ngay lập tức.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Mỗi số phụ thuộc vào đáp án tốt nhất cho các số nhỏ hơn có thể đạt được bằng cách trừ đi một chữ số.

Gợi ý 2

Quy hoạch động trên tất cả giá trị đến n giúp tránh tính lặp lại.

Gợi ý 3

Nhớ rằng các chữ số khả dụng thay đổi sau mỗi lần trừ, và 0 không bao giờ là lựa chọn hợp lệ.

Độ phức tạp mong đợi

thời gian O(n * d), bộ nhớ phụ O(n)

Tham khảo

Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

# Người giải Ngôn ngữ Thời gian Bộ nhớ AI đánh giá Lời giải
1 ННикита Python 942 ms - 2/5 Xem code

Học hỏi từ người khác

Giải pháp cộng đồng

Cảnh báo: Có 1 lời giải đầy đủ bên dưới Hãy thử tự giải trước. Bạn vẫn có thể xem mã của người khác và đánh giá AI. Đăng nhập và giải thử thách để tham gia thảo luận.