CHUYÊN ĐỀ QUY HOẠCH ĐỘNG

# CHUYÊN ĐỀ QUY HOẠCH ĐỘNG ## Chủ đề 1: Bài toán dãy con tăng dài nhất :::info Cho dãy số nguyên $A$ gồm $N$ phần tử. Một dãy con của $A$ là một cách chọn trong $A$ một số phần tử giữ nguyên thứ tự. Hãy cho biết độ dài của dãy con đơn điệu tăng dài nhất của $A$. *Nếu được, hãy cho biết dãy con kia.* ::: | INPUT | OUTPUT | Giải thích | | - | - | - | | 10 5 2 3 4 9 10 5 6 7 8 | 7 | Dãy con là 2, 3, 4, 5, 6, 7, 8 | :::success :::spoiler :key: **Đáp án giải pháp QHĐ** ```python= def dp_day_con_tang_dai_nhat(A): n = len(A) # Bảng phương án # Ở đây dp[i] có ý nghĩa là số phần tử trong mảng tăng # dài nhất có chứa phần tử A[i] trong đoạn A[0..i] dp = [1] * n # Mảng truy vết lưu chỉ số của phần tử trước đó # trong dãy con tăng trace = [-1] * n for i in range(1, n): for j in range(i): if A[i] > A[j] and dp[i] < dp[j] + 1: dp[i] = dp[j] + 1 trace[i] = j print(dp) gtln = max(dp) gtln_index = dp.index(gtln) # Xây dựng dãy con tăng dài nhất day_con_dai_nhat = [] while gtln_index != -1: day_con_dai_nhat.insert(0, A[gtln_index]) gtln_index = trace[gtln_index] return gtln, day_con_dai_nhat A = [5, 2, 3, 4, 9, 10, 5, 6, 7, 8] dai_nhat, day_con = dp_day_con_tang_dai_nhat(A) print("Độ dài của dãy con đơn điệu tăng dài nhất:", dai_nhat) print("Dãy con đơn điệu tăng dài nhất:", day_con) ``` ::: ### Bài toán 1: Bố trí phòng họp :::info Có $N$ cuộc họp đánh số từ $1$ đến $N$ đăng ký làm việc tại một phòng hội thảo. Cuộc họp thứ $i$ cần được bắt đầu ngay sau thời điểm $s_i$ và kết thúc tại thời điểm $f_i$. Hỏi có thể bố trí phòng hội thảo phục vụ được nhiều nhất bao nhiêu cuộc họp, sao cho khoảng thời gian làm việc của hai cuộc họp bất kỳ là không giao nhau. *Nếu được, hãy cho biết thứ tự thực hiện các cuộc họp đó.* ::: | INPUT | OUTPUT | Giải thích | | - | - | - | | 5 7 9 2 4 1 3 1 6 3 7 | 3 | Các cuộc họp diễn ra lần lượt là (1, 3) -> (3, 7) -> (7, 9) | :::success :::spoiler :key: **Đáp án giải pháp Tham lam** ```python= def tham_lam_sap_xep_cuoc_hop(ds_cuoc_hop): # Sắp xếp các cuộc họp theo thời điểm kết thúc tăng dần ds_cuoc_hop.sort(key=lambda x: x[1]) n = len(ds_cuoc_hop) ds_duoc_chon = [] # Danh sách cuộc họp được chọn # Thêm cuộc họp đầu tiên vào danh sách ds_duoc_chon.append(ds_cuoc_hop[0]) # Sắp xếp các cuộc họp còn lại for i in range(1, n): # Ta chỉ chọn một cuộc họp khi thời điểm bắt đầu cuộc họp # hiện tại >= thời điểm kết thúc cuộc họp cuối trong DS được chọn if ds_cuoc_hop[i][0] >= ds_duoc_chon[-1][1]: ds_duoc_chon.append(ds_cuoc_hop[i]) return ds_duoc_chon ds_cuoc_hop = [(7, 9), (2, 4), (1, 3), (1, 6), (3, 7)] ds_duoc_chon = tham_lam_sap_xep_cuoc_hop(ds_cuoc_hop) for bd, kt in ds_duoc_chon: print(bd, kt) ``` ::: :::success :::spoiler :key: **Đáp án giải pháp QHĐ** ```python= def dp_sap_xep_cuoc_hop(ds_cuoc_hop): n = len(ds_cuoc_hop) ds_cuoc_hop.sort(key=lambda x: x[1]) # Mảng dp để lưu số lượng cuộc họp tối đa có thể bố trí đến thời điểm kết thúc của cuộc họp dp = [1] * n # Tìm số lượng cuộc họp tối đa có thể bố trí đến thời điểm kết thúc của cuộc họp for i in range(1, n): for j in range(i): if ds_cuoc_hop[i][0] >= ds_cuoc_hop[j][1]: dp[i] = max(dp[i], dp[j] + 1) # Tìm số lượng cuộc họp tối đa có thể bố trí kq = max(dp) return kq ds_cuoc_hop = [(7, 9), (2, 4), (1, 3), (1, 6), (3, 7)] print(dp_sap_xep_cuoc_hop(ds_cuoc_hop)) ``` ::: ### Bài toán 2: Cho thuê máy :::info Trung tâm tính toán hiệu năng cao nhận được đơn đặt hàng của $N$ khách hàng. Khách hàng thứ $i$ muốn sử dụng máy trong khoảng thời gian từ $a_i$ đến $b_i$ và trả tiền thuê là $c_i$. Hãy bố trí lịch thuê máy để tổng số tiền thu được là lớn nhất mà thời gian sử dụng máy của 2 khách hàng bất kì được phục vụ đều không giao nhau (cả trung tâm chỉ có một máy cho thuê). Cho biết số tiền thu được nhiều nhất. *Nếu được, hãy cho biết thứ tự thuê máy.* ::: | INPUT | OUTPUT | Giải thích | | - | - | - | | 4 0 5 10 3 7 14 5 9 7 6 9 8 | 18 | Lần lượt là (0, 5, 10) -> (6, 9, 8) | :::success :::spoiler :key: **Đáp án giải pháp QHĐ** Về cách giải, bài này tương tự như bài trước nhưng ràng buộc để xây dựng bảng phương án `dp` sẽ nhắm vào việc tối đa hoá lợi nhuận. ```python= def dp_sap_xep_cho_thue(ds_thue): n = len(ds_thue) # Sắp xếp các đơn đặt hàng theo thời điểm kết thúc tăng dần ds_thue.sort(key=lambda x: x[1]) # Mảng dp để lưu tổng số tiền thu được tối đa # đến thời điểm kết thúc của đơn đặt hàng tương ứng dp = [0] * n dp[0] = ds_thue[0][2] # Tìm tổng số tiền thu được tối đa đến thời điểm kết thúc của đơn đặt hàng for i in range(1, n): # Nếu tiền cho thuê đơn này tốt hơn tiền cho thuê các đơn trước dp[i] = max(dp[i - 1], ds_thue[i][2]) for j in range(i - 1, -1, -1): if ds_thue[i][0] >= ds_thue[j][1]: dp[i] = max(dp[i], dp[j] + ds_thue[i][2]) # Tìm tổng số tiền thu được lớn nhất kq = max(dp) return kq ds_thue = [(0, 5, 10), (3, 7, 14), (5, 9, 7), (6, 9, 8)] print(dp_sap_xep_cho_thue(ds_thue)) ``` ::: --- ## Chủ đề 2: Chiếc balo (dạng 1) :::info Có $N$ đồ vật, đồ vật thứ $i$ có trọng lượng $A_i$ và giá trị là $B_i$. Hãy chọn ra một số các đồ vật, mỗi vật một cái để xếp vào 1 chiếc balo có thể chứa trọng lượng tối đa là $W$ sao cho tổng giá trị của balo là lớn nhất. Hãy cho biết tổng giá trị lớn nhất đó. ::: | INPUT | OUTPUT | Giải thích | | - | - | - | | 3 8 3 30 4 50 5 60 | 90 | Chọn vật thứ 1 và 3 | :::success :::spoiler :key: **Đáp án giải pháp đệ quy** ```python= def de_quy_ba_lo_1(A, B, W, n): if n == 0 or W == 0: return 0 if A[n - 1] > W: return de_quy_ba_lo_1(A, B, W, n - 1) return max( # Phương án 1: chọn đồ vật này, ba lô bị giảm sức chứa B[n - 1] + de_quy_ba_lo_1(A, B, W - A[n - 1], n - 1), # Phương án 2: bỏ qua đồ vật này, ba lô còn nguyên sức chứa de_quy_ba_lo_1(A, B, W, n - 1) ) N, W = 3, 8 A = [3, 4, 5] B = [30, 50, 60] print(de_quy_ba_lo_1(A, B, W, N)) ``` ::: :::success :::spoiler :key: **Đáp án giải pháp QHĐ** ```python= def dp_ba_lo_1(A, B, W, N): # Tạo một bảng phương án 2 chiều để lưu trữ giá trị tối ưu # cho từng trọng lượng và số lượng đồ vật dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)] # Xây dựng bảng phương án for i in range(1, N + 1): for w in range(W + 1): if A[i - 1] <= w: # Nếu ba lô có trọng lượng w chứa được vật thứ i dp[i][w] = max( # Chọn vật i B[i - 1] + dp[i - 1][w - A[i - 1]], # Không chọn vật i dp[i - 1][w] ) else: dp[i][w] = dp[i - 1][w] # Trả về giá trị tối ưu ở ô cuối cùng của bảng động ứng với N và W return dp[N][W] N, W = 3, 8 A = [3, 4, 5] B = [30, 50, 60] print(dp_ba_lo_1(A, B, W, N)) ``` ::: ### Bài toán 1: Dãy con có tổng bằng $S$ :::info Cho dãy số $A$ có $N$ phần tử. Tìm dãy con của $A$ có tổng đúng bằng $S$. Nếu có một dãy con như vậy thì in ra chữ `YES`. *Nếu được, cho biết các số được chọn.* ::: | INPUT | OUTPUT | Giải thích | | - | - | - | | 5 6 1 2 4 3 5 | YES | Chọn số 1 2 và 3 hoặc 2 và 4 hoặc 1 và 5 | :::success :::spoiler :key: **Đáp án giải pháp QHĐ** ```python= def dp_day_con_tong_S(A, N, S): # Bảng phương án 2 chiều dp = [[False for _ in range(S + 1)] for _ in range(N + 1)] # Bài toán cơ sở for i in range(N + 1): dp[i][0] = True for i in range(1, N + 1): for j in range(1, S + 1): if A[i - 1] > j: dp[i][j] = dp[i - 1][j] else: dp[i][j] = dp[i - 1][j] or dp[i - 1][j - A[i - 1]] return dp[N][S] N, S = 5, 6 A = [1, 2, 4, 3, 5] print("YES" if dp_day_con_tong_S(A, N, S) else "NO") ``` ::: ### Bài toán 2: Chia kẹo :::info Có $N$ gói kẹo, gói thứ $i$ có $A_i$ cái kẹo. Không được bóc bất kỳ một gói kẹo nào, cần chia $N$ gói kẹo thành hai phần sao cho độ chênh lệch số kẹo giữa hai gói là ít nhất. Cho biết độ chênh lệch đó. ::: | INPUT | OUTPUT | Giải thích | | - | - | - | | 6 7 1 2 5 9 6 | 0 | Phần đầu gồm các gói (7, 2, 6) phần sau gồm các gói (1, 5, 9) | :::success :::spoiler :key: **Đáp án giải pháp QHĐ** ```python= def dp_chia_keo(A, N): tong = sum(A) # Tạo mảng để lưu trữ thông tin về cách chia gói kẹo thành hai phần # dp[i][j] là True nếu có thể chia i gói kẹo thành hai phần sao cho độ chênh lệch số kẹo là j dp = [[False for _ in range(tong + 1)] for _ in range(N + 1)] # Một phần không chứa kẹo có độ chênh lệch là 0 for i in range(N + 1): dp[i][0] = True # Xây dựng bảng phương án for i in range(1, N + 1): for j in range(tong + 1): if A[i - 1] > j: dp[i][j] = dp[i - 1][j] else: dp[i][j] = dp[i - 1][j] or dp[i - 1][j - A[i - 1]] # Tìm giá trị chính xác của độ chênh lệch nhỏ nhất khac_nhau = float('inf') for j in range(tong // 2 + 1): if dp[N][j]: khac_nhau = min(khac_nhau, tong - 2 * j) return khac_nhau N = 6 A = [7, 1, 2, 5, 9, 6] print(dp_chia_keo(A, N)) ``` ::: ### Bài toán 3: Điền dấu biểu thức :::info Cho $N$ số tự nhiên $A_1,A_2,...,A_N$. Ban đầu các số được đặt liên tiếp theo đúng thứ tự cách nhau bởi dấu "$?$": $A_1\ ?\ A_2\ ?\ ...\ ?\ A_N$. Cho trước số nguyên $S$, có cách nào thay các dấu $?$ bằng dấu $+$ hay dấu $−$ để được một biểu thức số học cho giá trị là $S$ không? ::: | INPUT | OUTPUT | Giải thích | | - | - | - | | 4 0 1 2 3 4 | YES | Ta điền $1-2-3+4=0$ | :::success :::spoiler :key: **Đáp án giải pháp QHĐ** ```python= def dp_dien_dau(A, N, S): tong = sum(A) if tong % 2 != 0 or S % 2 != 0: return False muc_tieu = S // 2 dp = [[False for _ in range(muc_tieu + 1)] for _ in range(N + 1)] for i in range(N + 1): dp[i][0] = True for i in range(1, N + 1): for j in range(1, muc_tieu + 1): if A[i - 1] <= j: dp[i][j] = dp[i - 1][j] or dp[i - 1][j - A[i - 1]] else: dp[i][j] = dp[i - 1][j] return dp[N][muc_tieu] N, S = 4, 0 A = [1, 2, 3, 4] print("YES" if dp_dien_dau(A, N, S) else "NO") ``` ::: --- ## Chủ đề 3: Chiếc balo (dạng 2) :::info Cho $N$ vật, vật $i$ nặng $A_i$ và có giá trị $B_i$. Hãy chọn ra một số vật để cho vào balô sao cho tổng khối lượng không vượt quá $W$ và tổng giá trị là lớn nhất. Cho biết giá trị lớn nhất đó. Chú ý rằng mỗi vật có thể được chọn nhiều lần. ::: | INPUT | OUTPUT | Giải thích | | - | - | - | | 4 37 15 30 10 25 2 2 4 6 | 83 | | :::success :::spoiler :key: **Đáp án giải pháp QHĐ** Ở những bài có công thức truy hồi chỉ phụ thuộc vào dòng trước đó và dòng hiện tại của bảng phương án, chỉ cần dùng mảng 1 chiều là đủ. ```python= def dp_ba_lo_2(A, B, N, W): # Khởi tạo bảng phương án dp = [[0] * (W + 1) for _ in range(N + 1)] # Xây dựng bảng phương án for i in range(1, N + 1): for j in range(W + 1): if A[i - 1] <= j: dp[i][j] = max( # Không chọn vật i dp[i - 1][j], # Chọn vật i dp[i][j - A[i - 1]] + B[i - 1] ) else: dp[i][j] = dp[i - 1][j] return dp[N][W] N, W = 4, 37 A = [15, 10, 2, 4] B = [30, 25, 2, 6] print(dp_ba_lo_2(A, B, N, W)) ``` ::: :::success :::spoiler :key: **Đáp án giải pháp QHĐ (cài đặt 2)** ```python= def dp_ba_lo_2(A, B, N, W): # Khởi tạo bảng phương án dp = [0] * (W + 1) # Xây dựng bảng phương án for i in range(1, W + 1): for j in range(N): if A[j] <= i: dp[i] = max(dp[i], dp[i - A[j]] + B[j]) return dp[W] N, W = 4, 37 A = [15, 10, 2, 4] B = [30, 25, 2, 6] print(dp_ba_lo_2(A, B, N, W)) ``` ::: ### Bài toán 1: Đổi tiền :::info Ở đất nước Omega người ta chỉ tiêu tiền xu. Có $N$ loại tiền xu, loại thứ $i$ có mệnh giá là $A_i$ đồng. Một người khách du lịch đến Omega du lịch với số tiền $M$ đồng. Ông ta muốn đổi số tiền đó ra tiền xu Omega để tiện tiêu dùng. Ông ta cũng muốn số đồng tiền đổi được là ít nhất (cho túi tiền đỡ nặng khi đi đây đi đó). Bạn hãy giúp ông ta tìm cách đổi tiền. ::: | INPUT | OUTPUT | Giải thích | | - | - | - | | 4 11 1 3 5 7 | 3 | 2 đồng 5 xu và 1 đồng 1 xu | :::success :::spoiler :key: **Đáp án giải pháp QHĐ** Trong bài này, ta xem các loại tiền chính là các món đồ vật với khối lượng tương ứng và $M$ chính là sức chứa tối đa của chiếc ba lô. ```python= def dp_doi_tien(loai_tien_xu, m): # dp[i] hiểu là số xu tối thiểu đổi được từ i đồng dp = [float('inf')] * (m + 1) dp[0] = 0 for loai in loai_tien_xu: for i in range(loai, m + 1): dp[i] = min(dp[i], dp[i - loai] + 1) return dp[m] if dp[m] != float('inf') else -1 m = 11 loai_tien_xu = [1, 3, 5, 7] print(dp_doi_tien(loai_tien_xu, m)) ``` ::: --- ## Chủ đề 4: Biến đổi xâu :::info Cho 2 xâu $X$ và $F$. Xâu gốc $X$ có $n$ kí tự từ $X_1, X_2,...,X_n$, xâu đích $F$ có $m$ kí tự $F_1, F_2,...,F_n$. Có 3 phép biến đổi (3 loại truy vấn): - Loại 1: chèn 1 kí tự vào sau kí tự thứ $i$: $1\ i\ c$ (với $c$ là ký tự cần chèn) - Loại 2: thay thế kí tự ở vị trí thứ $i$ bằng kí tự $c$: $2\ i\ c$ - Loại 3: xoá kí tự ở vị trí thứ $i$: $3\ i$ Hãy tìm số ít nhất các phép biến đổi để biến xâu $X$ thành xâu $F$. ::: | INPUT | OUTPUT | Giải thích | | - | - | - | | 6 7 kitten sitting | 3 | Thứ tự thực hiện các truy vấn có thể như sau: 2 1 s 2 5 i 1 7 g | :::success :::spoiler :key: **Đáp án giải pháp QHĐ** ```python= def dp_bien_doi_xau(X, F): n, m = len(X), len(F) # Tạo mảng dp có kích thước (n+1) x (m+1) # Ta gọi dp[i][j] là số phép biến đổi tối thiểu để biến xâu # X[..i] thành xâu F[..j] dp = [[0] * (m + 1) for _ in range(n + 1)] # Điền bảng phương án for i in range(n + 1): for j in range(m + 1): if i == 0: dp[i][j] = j # Bài toán cơ sở: # Nếu xâu X rỗng, cần thực hiện j phép chèn elif j == 0: dp[i][j] = i # Bài toán cơ sở: # Nếu xâu F rỗng, cần thực hiện i phép xoá elif X[i - 1] == F[j - 1]: # TH1: 2 ký tự giống nhau dp[i][j] = dp[i - 1][j - 1] else: # TH2: 2 ký tự khác nhau => tìm min giữa 3 cách dp[i][j] = 1 + min(dp[i - 1][j], # Xoá dp[i][j - 1], # Chèn dp[i - 1][j - 1]) # Thay thế return dp[n][m] X = "kitten" F = "sitting" print(dp_bien_doi_xau(X, F)) ``` ::: ### Bài toán 1: Xâu con chung dài nhất :::info Cho 2 xâu $X$ và $Y$. Hãy tìm xâu con của $X$ và của $Y$ có độ dài lớn nhất. Biết xâu con của một xâu thu được khi xóa một số kí tự thuộc xâu đó (hoặc không xóa kí tự nào). Tìm độ dài xâu con chung dài nhất đó. ::: | INPUT | OUTPUT | Giải thích | | - | - | - | | 4 6 **ABCA** B**ABCA**B | 4 | Xâu chung là **ABCA** | :::success :::spoiler :key: **Đáp án giải pháp QHĐ** ```python= def dp_xau_chung_dai_nhat(X, Y): m = len(X) n = len(Y) # Tạo bảng phương án dp = [[0] * (n + 1) for _ in range(m + 1)] # Xây dựng bảng theo quy hoạch động for i in range(1, m + 1): for j in range(1, n + 1): if X[i - 1] == Y[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # Độ dài của xâu con chung lớn nhất return dp[m][n] X = "ABCA" Y = "BABCAB" print(dp_xau_chung_dai_nhat(X, Y)) ``` ::: ### Bài toán 2: Palindrome :::info Một xâu gọi là xâu đối xứng (palindrome) nếu xâu đó đọc từ trái sang phải hay từ phải sang trái đều như nhau. Cho một xâu $S$ gồm $N$ kí tự $S_1,...S_N$, hãy tìm số kí tự ít nhất cần thêm vào $S$ để $S$ trở thành xâu đối xứng. ::: | INPUT | OUTPUT | Giải thích | | - | - | - | | 7 EDBABCD | 2 | Ta cần thêm 2 ký tự là **C** và **E** để thành xâu ED**C**BABCD**E** | :::success :::spoiler :key: **Đáp án giải pháp QHĐ** ```python= def dp_xau_chung_dai_nhat(X, Y): m = len(X) n = len(Y) # Tạo bảng phương án dp = [[0] * (n + 1) for _ in range(m + 1)] # Xây dựng bảng theo quy hoạch động for i in range(1, m + 1): for j in range(1, n + 1): if X[i - 1] == Y[j - 1]: dp[i][j] = dp[i - 1][j - 1] + 1 else: dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # Độ dài của xâu con chung lớn nhất return dp[m][n] def so_ky_tu_them_de_doi_xung(S): # Tính xâu đảo ngược của S S_reverse = S[::-1] # Tính độ dài của xâu chung lớn nhất len_longest_common = dp_xau_chung_dai_nhat(S, S_reverse) # Số ký tự ít nhất cần thêm vào để trở thành xâu đối xứng return len(S) - len_longest_common S = "EDBABCD" print(so_ky_tu_them_de_doi_xung(S)) ``` ::: --- ## Chủ đề 5: Nhân ma trận :::info Nhân một ma trận kích thước $m \times n$ với một ma trận $n \times p$, số phép nhân phải thực hiện là $m \times n \times p$. Mặt khác phép nhân các ma trận có tính kết hợp, tức là: $(A \times B) \times C = A \times (B \times C)$ Do đó khi tính tích nhiều ma trận, ta có thể thực hiện theo các trình tự khác nhau, mỗi trình tự tính sẽ quyết định số phép nhân cần thực hiện. Cho $N$ ma trận $A_1,A_2,...,A_N$ ma trận $A$ có kích thước là $d_{i-1} \times d_i$. Hãy xác định trình tự nhân ma trận $A_1,A_2,...,A_N$ sao cho số phép nhân cần thực hiện là ít nhất. Cho biết số phép nhân đó là bao nhiêu? ::: ### Bài toán 1: Biểu thức số học :::info Cho biểu thức gồm $N$ toán hạng $A_1\ ?\ A_2\ ?\ ...\ ?\ A_N$, trong đó $A_i$ là các số thực không âm và $?$ là một phép toán $+$ hoặc $*$ cho trước (ta không cần quan tâm). Hãy đặt các dấu ngoặc để biểu thức thu được có kết quả lớn nhất. Tìm ra giá trị lớn nhất đó. ::: --- ## Chủ đề 6: Ghép cặp :::info Có $n$ lọ hoa sắp thẳng hàng và $k$ bó hoa được đánh số thứ tự từ nhỏ đến lớn. Cần cắm $k$ bó hoa trên vào $n$ lọ sao cho hoa có số thứ tự nhỏ phải đứng trước hoa có số thứ tự lớn. Giá trị thẩm mỹ tương ứng khi cắm hoa $i$ vào lọ thứ $j$ là $v(i,j)$. Hãy tìm 1 cách cắm sao cho tổng giá trị thẫm mỹ là lớn nhất. Chú ý rằng mỗi bó hoa chỉ được cắm vào 1 lọ và mỗi lọ cũng chỉ cắm được 1 bó hoa. Tìm ra giá trị thẩm mỹ lớn nhất đó. ::: | INPUT | OUTPUT | Giải thích | | - | - | - | | 3 2 1 2 3 2 1 3 | 5 | Ta cắm hoa số 1 vào lọ 2 và hoa số 2 vào lọ 3 | :::success :::spoiler :key: **Đáp án giải pháp QHĐ** ```python= def dp_cam_hoa(n, k, v): # Bảng phương án dp = [[0] * (n + 1) for _ in range(k + 1)] for i in range(1, k + 1): # hoa for j in range(1, n + 1): # lọ if i > j: # TH1: i > j -> không có cách cắm nào dp[i][j] = 0 elif i == j: # TH2: i = j -> chỉ có 1 cách duy nhất dp[i][j] = dp[i - 1][j - 1] + v[i - 1][j - 1] else: # TH3: i < j -> cấm hoa i vào lọ j hoặc lọ trước j dp[i][j] = max( # cấm vào lọ trước j dp[i][j - 1], # cấm luôn vào lọ j dp[i - 1][j - 1] + v[i - 1][j - 1] ) return dp[k][n] n = 3 k = 2 v = [ [1, 2, 3], [2, 1, 3] ] print(dp_cam_hoa(n, k, v)) ``` ::: ### Bài toán 1: Câu lạc bộ :::info Có $n$ phòng học chuyên đề và $k$ nhóm học được đánh số thứ tự từ nhỏ đến lớn. Cần xếp $k$ nhóm trên vào $n$ phòng học sao cho nhóm có số hiệu nhỏ được xếp vào phòng có số hiệu nhỏ, nhóm có số hiệu lớn phải được xếp vào phòng có số hiệu lớn. Với mỗi phòng có chứa học sinh, các ghế thừa phải được chuyển ra hết, nếu thiếu ghế thì lấy vào cho đủ ghế. Biết phòng $i$ có $A_i$ ghế, nhóm $j$ có $B_j$ học sinh. Hãy chọn 1 phương án bố trí sao cho tổng số lần chuyển ghế ra và vào là ít nhất. Hãy tìm ra số lần chuyển ít nhất đó. ::: --- ## Chủ đề 7: Di chuyển :::info Cho bảng $A$ gồm $M \times N$ ô. Từ ô $(i,j)$ có thể di chuyển sang 3 ô $(i+1,j)$, $(i+1,j−1)$ và $(i+1,j+1)$. Hãy xác định một lộ trình đi từ hàng 1 đến hàng $M$ sao cho tổng các ô đi qua là lớn nhất. ::: | INPUT | OUTPUT | Giải thích | | - | - | - | | 3 4 1 2 3 4 4 1 6 8 7 8 9 10 | 22 | Ta đi đường 4 -> 8 -> 10 | :::success :::spoiler :key: **Đáp án giải pháp QHĐ** ```python= def dp_tim_duong(A): M, N = len(A), len(A[0]) # Bảng phương án dp = [[0] * N for _ in range(M)] # Gán giá trị cho hàng đầu tiên của DP # bằng giá trị của hàng đầu tiên của bảng for j in range(N): dp[0][j] = A[0][j] # Duyệt qua các hàng từ start_i + 1 đến M for i in range(1, M): for j in range(N): # Tìm giá trị tối ưu tại ô (i, j) dựa trên các ô trước đó dp[i][j] = A[i][j] + max( dp[i-1][j], dp[i-1][max(0, j-1)], dp[i-1][min(N-1, j+1)] ) # Tìm giá trị lớn nhất trong hàng cuối cùng của DP return max(dp[M-1]) A = [ [1, 2, 3, 4], [4, 1, 6, 8], [7, 8, 9, 10] ] print(dp_tim_duong(A)) ``` ::: ---