Hai tính chất cốt lõi bắt buộc phải có của một bài toán để có thể giải được bằng phương pháp Quy hoạch động là gì?, Tính toán song song và Chia để trị., Bài toán con trùng lặp (Overlapping Subproblems) và Cấu trúc con tối ưu (Optimal Substructure)., Khử đệ quy và Tối ưu hóa bộ nhớ tham lam., Sắp xếp dữ liệu và Tìm kiếm nhị phân., Trong bài toán Dãy con tăng dài nhất (LIS), nếu gọi DP[i] là độ dài của dãy con tăng dài nhất kết thúc tại phần tử A[i], công thức truy hồi nào sau đây là đúng?, DP[i] = max(DP[j]) + 1 với mọi 0 <= j < i, DP[i] = DP[i-1] + 1 nếu A[i] > A[i-1], DP[i] = max(DP[j]) + 1 với mọi 0 \<= j < i và A[j] < A[i], DP[i] = max(DP[i-1], DP[i-2]), Sự khác biệt cốt lõi giữa phương pháp Tiếp cận từ dưới lên (Bottom-up / Tabulation) và Tiếp cận từ trên xuống (Top-down / Memoization) là gì?, Bottom-up dùng vòng lặp để lấp đầy bảng phương án từ các bài toán cơ sở nhỏ nhất, còn Top-down dùng đệ quy có nhớ., Bottom-up dùng đệ quy để đi từ bài toán lớn xuống, còn Top-down dùng vòng lặp., Bottom-up chỉ áp dụng được cho mảng 1 chiều, còn Top-down áp dụng cho mảng 2 chiều., Top-down luôn chạy nhanh hơn và tốn ít bộ nhớ hơn Bottom-up., Ưu điểm lớn nhất của việc áp dụng Quy hoạch động (lưu trữ kết quả bài toán con) so với thuật toán Đệ quy thuần túy khi giải bài toán tìm số Fibonacci thứ n là gì?, Giúp mã nguồn ngắn hơn và không cần sử dụng mảng hay bộ nhớ phụ., Giảm độ phức tạp không gian lưu trữ xuống $O(1)$ mà không làm thay đổi thời gian chạy., Giúp ngăn chặn hoàn toàn hiện tượng tràn số nguyên khi $n$ quá lớn., Giảm độ phức tạp thời gian từ hàm mũ $O(2^n)$ xuống độ phức tạp tuyến tính $O(n)$ bằng cách tránh tính toán lại., Cho bài toán Di chuyển trên lưới ô vuông: Bạn xuất phát từ ô (1, 1), chỉ được đi sang phải hoặc xuống dưới để đến ô (M, N) sao cho tổng điểm nhận được là lớn nhất. Gọi DP[i][j] là tổng điểm lớn nhất khi đi từ (1, 1) đến ô (i, j), và A[i][j] là điểm số tại ô đó. Công thức xác định DP[i][j] là gì?, DP[i][j] = max(DP[i-1][j], DP[i][j-1]) + A[i][j], DP[i][j] = DP[i-1][j-1] + A[i][j], DP[i][j] = min(DP[i-1][j], DP[i][j-1]) + A[i][j], DP[i][j] = DP[i-1][j] + DP[i][j-1] + A[i][j]

DYNAMIC PROGRAMMING

von
Drucken
Einbetten

Bestenliste

Visueller Stil

Einstellungen

Vorlage ändern

Soll die automatisch gespeicherte Aktivität wiederhergestellt werden?