Mọi lộ trình

Quy hoạch động và tối ưu hóa

Giải các quyết định khó của nhiệm vụ không gian bằng bảng trên Raspberry Pi: bài toán con chồng lấn, đổi tiền, knapsack, khoảng cách chỉnh sửa, tham lam đối chiếu quy hoạch động, xếp lịch, và bộ lập lộ trình giữa các trạm.

Raspberry Pi 4 Model BMiễn phí7 bài học5 h4 chương2.530 XPLập trình · Nâng cao+250 XP

Đã hoàn thành 0 trên 7

Bạn sẽ làm được gì

3 dự án, làm từng bước một

7 bài học trong 4 chương, khoảng 5 giờ trên một Raspberry Pi 4 Model B được mô phỏng. Miễn phí, ngay trong trình duyệt, mỗi bước đều được trình mô phỏng kiểm tra.

Dự án chương 1

Đổi xu

Các cú đẩy động cơ với kích thước cố định: tham lam chọn ba cú trong khi hai cú là đủ, một bảng DP tìm số cú ít nhất, bảng chọn cho biết là những cú nào, một bảng DP thứ hai đếm mọi cách phối hợp, và tính khả năng tiếp cận cho thấy những tốc độ nào không bao giờ chạm tới.

Mở trong trình mô phỏng
Dự án chương 2

Khoảng cách chỉnh sửa

Các lệnh bị nhiễu từ một que đo: vì sao đếm các vị trí lệch nhau lại thất bại, bảng Levenshtein, cách in bảng, lần ngược bảng để ra danh sách các sửa đổi, và một dòng lệnh trả lời "ý bạn là DEPLOY?"

Mở trong trình mô phỏng
Dự án chương 3

Lập lịch

Lập lịch khoảng có trọng số: khi các lượt truyền mang lượng dữ liệu khác nhau, chọn kết thúc sớm nhất trước sẽ mất 15 MB. Một quy hoạch động với bisect tìm lịch tốt nhất, lần ngược bảng để chỉ ra lịch đó, LED đỏ theo dõi nó theo thời gian, và một đường quét đếm ăng-ten.

Mở trong trình mô phỏng
Bản đồ

Từng chương một

Mỗi bài học mở ra khi bài trước hoàn thành, và mỗi chương kết thúc bằng một dự án.

Chương 1

Tư duy bằng bảng

Nhận ra công việc lặp lại và thay bằng một bảng được điền từ dưới lên.

  1. Mở250 XP

    Bài toán con chồng lấp

    Một chiếc thang dock leo mỗi lần 1, 2 hoặc 3 bậc: hãy xem cùng một bài toán con được giải hàng trăm lần, ghi nhớ kết quả (memoize), biến nó thành bảng điền từ dưới lên, và thu bảng còn ba con số để leo 1000 bậc, điều mà đệ quy không làm nổi.

    0/5 bước

  2. Dự ánĐã khóa500 XP

    Đổi xu

    Các cú đẩy động cơ với kích thước cố định: tham lam chọn ba cú trong khi hai cú là đủ, một bảng DP tìm số cú ít nhất, bảng chọn cho biết là những cú nào, một bảng DP thứ hai đếm mọi cách phối hợp, và tính khả năng tiếp cận cho thấy những tốc độ nào không bao giờ chạm tới.

    0/5 bước

5 câu hỏi, được chấm ngay khi bạn trả lời.
Chương 2

Những lỗi kinh điển

Đóng gói tên lửa và sửa một lệnh bị nhiễu, với hai bảng nổi tiếng nhất.

  1. Đã khóa250 XP

    Bài toán balo

    Đóng 10 kg cuối cùng của tên lửa để thu nhiều kết quả khoa học nhất: vét cạn 256 phương án, bảng balo 0/1, phục hồi phương án được chọn, phiên bản một hàng và lỗi kinh điển khi lặp theo chiều sai, rồi 30 thùng hàng mà vét cạn không bao giờ thử nổi.

    0/5 bước

  2. Dự ánĐã khóa500 XP

    Khoảng cách chỉnh sửa

    Các lệnh bị nhiễu từ một que đo: vì sao đếm các vị trí lệch nhau lại thất bại, bảng Levenshtein, cách in bảng, lần ngược bảng để ra danh sách các sửa đổi, và một dòng lệnh trả lời "ý bạn là DEPLOY?"

    0/5 bước

4 câu hỏi, được chấm ngay khi bạn trả lời.
Chương 3

Tham lam hay quy hoạch động

Khi nào một lựa chọn nhanh được chứng minh là đúng, và khi nào chỉ bảng mới giải được.

  1. Đã khóa227 XP

    Tham lam đối chiếu quy hoạch động

    Khi nào một lựa chọn tham lam nhanh được chứng minh là đúng và khi nào nó thất bại: các lượt vệ tinh theo kết thúc sớm nhất đối chiếu ngắn nhất trước, các bình nhiên liệu chia được đối chiếu không chia được, và một phép thử cho biết hệ đồng xu nào tham lam xử lý được.

    0/5 bước

  2. Dự ánĐã khóa500 XP

    Lập lịch

    Lập lịch khoảng có trọng số: khi các lượt truyền mang lượng dữ liệu khác nhau, chọn kết thúc sớm nhất trước sẽ mất 15 MB. Một quy hoạch động với bisect tìm lịch tốt nhất, lần ngược bảng để chỉ ra lịch đó, LED đỏ theo dõi nó theo thời gian, và một đường quét đếm ăng-ten.

    0/5 bước

4 câu hỏi, được chấm ngay khi bạn trả lời.
Chương 4

Dự án

Một bộ hoạch định tuyến cho phà giữa các trạm không gian.

  1. Đã khóa303 XP

    Dự án: bộ hoạch định tuyến

    Dự án: bộ hoạch định tuyến phà giữa các trạm không gian. Thời gian ngắn nhất bằng quy hoạch động theo thứ tự trạm, lần ngược để lấy tuyến, tuyến tốt nhất trong một số chặng (các vòng Bellman-Ford), và một bộ hoạch định trên bộ đèn giao thông nhận điểm đến qua serial.

    0/7 bước

3 câu hỏi, được chấm điểm ngay khi bạn làm.
Chứng chỉ

Chứng chỉ khi bạn hoàn thành

Hoàn thành mọi bài học và vượt qua mọi bài kiểm tra cuối chương, Mokxi sẽ cấp chứng chỉ ghi tên bạn, được xác minh trên trang riêng của nó.

Số chứng chỉ:MXC0-URSE-0001

Chứng chỉ Hoàn thành

Chứng nhận rằng

Tên Của Bạn

đã hoàn thành tốt khóa học

Quy hoạch động và tối ưu hóa

Bao gồm Tư duy bằng bảng, Các bài toán kinh điển, Tham lam hay quy hoạch động và Dự án.

7 bài học · khoảng 5 giờ học

DaneDane, Nhà sáng lập, MokxiCấp ngày 17 tháng 11, 2026
Xác minh chứng chỉ nàymokxi.com/cert/MXC0URSE0001
Chứng chỉ

Nhận chứng chỉ của bạn

  • Tên bạn và một mã số duy nhấtIn trên chứng chỉ khổ ngang thuộc về bạn.
  • Được Mokxi xác minhMã QR và trang công khai để ai cũng có thể kiểm tra.
  • Thêm vào LinkedInMột cú nhấp điền sẵn biểu mẫu chứng chỉ trên LinkedIn.
  • Tải về PDFIn ra hoặc đính kèm vào CV hay hồ sơ xin việc.

Hoàn thành khóa học để nhận chứng chỉ có thể xác minh, ghi tên bạn, kèm mã QR và liên kết cho LinkedIn. Chứng chỉ đi kèm gói Pro, và 7 ngày dùng thử miễn phí.

Nội dung khóa học

Mọi bài học trong khóa

Tất cả 7 bài học, theo thứ tự, kèm nội dung mỗi bài. Bất kỳ bài nào cũng mở ngay trong trình soạn code.

Chương 1

Tư duy bằng bảng

  1. Bài toán con chồng lấpMột chiếc thang dock leo mỗi lần 1, 2 hoặc 3 bậc: hãy xem cùng một bài toán con được giải hàng trăm lần, ghi nhớ kết quả (memoize), biến nó thành bảng điền từ dưới lên, và thu bảng còn ba con số để leo 1000 bậc, điều mà đệ quy không làm nổi.
  2. Đổi xuCác cú đẩy động cơ với kích thước cố định: tham lam chọn ba cú trong khi hai cú là đủ, một bảng DP tìm số cú ít nhất, bảng chọn cho biết là những cú nào, một bảng DP thứ hai đếm mọi cách phối hợp, và tính khả năng tiếp cận cho thấy những tốc độ nào không bao giờ chạm tới.
Chương 2

Những lỗi kinh điển

  1. Bài toán baloĐóng 10 kg cuối cùng của tên lửa để thu nhiều kết quả khoa học nhất: vét cạn 256 phương án, bảng balo 0/1, phục hồi phương án được chọn, phiên bản một hàng và lỗi kinh điển khi lặp theo chiều sai, rồi 30 thùng hàng mà vét cạn không bao giờ thử nổi.
  2. Khoảng cách chỉnh sửaCác lệnh bị nhiễu từ một que đo: vì sao đếm các vị trí lệch nhau lại thất bại, bảng Levenshtein, cách in bảng, lần ngược bảng để ra danh sách các sửa đổi, và một dòng lệnh trả lời "ý bạn là DEPLOY?"
Chương 3

Tham lam hay quy hoạch động

  1. Tham lam đối chiếu quy hoạch độngKhi nào một lựa chọn tham lam nhanh được chứng minh là đúng và khi nào nó thất bại: các lượt vệ tinh theo kết thúc sớm nhất đối chiếu ngắn nhất trước, các bình nhiên liệu chia được đối chiếu không chia được, và một phép thử cho biết hệ đồng xu nào tham lam xử lý được.
  2. Lập lịchLập lịch khoảng có trọng số: khi các lượt truyền mang lượng dữ liệu khác nhau, chọn kết thúc sớm nhất trước sẽ mất 15 MB. Một quy hoạch động với bisect tìm lịch tốt nhất, lần ngược bảng để chỉ ra lịch đó, LED đỏ theo dõi nó theo thời gian, và một đường quét đếm ăng-ten.
Chương 4

Dự án

  1. Dự án: bộ hoạch định tuyếnDự án: bộ hoạch định tuyến phà giữa các trạm không gian. Thời gian ngắn nhất bằng quy hoạch động theo thứ tự trạm, lần ngược để lấy tuyến, tuyến tốt nhất trong một số chặng (các vòng Bellman-Ford), và một bộ hoạch định trên bộ đèn giao thông nhận điểm đến qua serial.
Bộ kit

Cùng lắp trên bàn thực hành của bạn

Mỗi bài học đều chạy trong trình mô phỏng, không cần mua gì. Khi bạn muốn làm thật, các bộ kit này có sẵn linh kiện.

Đã có kit rồi?

Tìm kit của bạn

Chọn bộ kit khởi đầu bạn đang có và chạy mọi bài học trong sách hướng dẫn với cùng linh kiện trên cùng các chân.

Xem tất cả các kit
Câu hỏi

Giới thiệu về Quy hoạch động và tối ưu hóa

Quy hoạch động và tối ưu hóa có miễn phí không?

Có. Cả 7 bài học của Quy hoạch động và tối ưu hóa đều miễn phí và chạy ngay trong trình duyệt, không cần cài gì và không phải mua linh kiện nào trước khi bắt đầu.

Tôi có cần một Raspberry Pi 4 Model B thật không?

Không. Mỗi bài học chạy trên một Raspberry Pi 4 Model B được mô phỏng với các linh kiện trên khung vẽ, và trình mô phỏng kiểm tra từng bước khi bạn làm. Khi bạn muốn lắp thật, cách nối dây và code giống hệt sẽ chạy được trên bo mạch thật.

Quy hoạch động và tối ưu hóa mất bao lâu?

Khoảng 5 giờ: 7 bài học trong 4 chương, mỗi bài gồm vài bước ngắn. Tiến độ được lưu, nên bạn có thể dừng sau bất kỳ bài nào rồi tiếp tục từ chỗ đã dừng.

Mình sẽ làm được gì?

Mỗi chương kết thúc bằng một dự án gom lại tất cả: Đổi tiền, Khoảng cách chỉnh sửa và Lập lịch.

Bắt đầu từ đâu?

Bắt đầu với "Bài toán con chồng lấp", và mỗi bài học xây trên bài trước đó. Mới học về mạch? Điện tử cơ bản là khóa học bắt đầu từ số không.