SKKN Sử dụng phương pháp quy hoạch động trong bồi dưỡng học sinh giỏi cấp tỉnh môn Tin Học

SỞ GIÁO DỤC VÀ ĐÀO TẠO THANH HOÁ
TRƯỜNG THPT CHUYÊN LAM SƠN
SÁNG KIẾN KINH NGHIỆM 
SỬ DỤNG PHƯƠNG PHÁP QUY HOẠCH ĐỘNG TRONG BỒI DƯỠNG HSG CẤP TỈNH MÔN TIN HỌC 
 Người thực hiện: Nguyễn Thị Huyền
 Chức vụ: Giáo viên
 SKKN thuộc môn:Tin học
THANH HÓA NĂM 2016
MỤC LỤC
Trang
I. Mở đầu
1
1. Lý do chọn đề tài
1
2. Mục đích nghiên cứu.
2
II. Nội dung
1. Cơ sở lý luận
2
2
2. Một số bài toán quy hoạch động điển hình.
6
a. Dãy con đơn điệu dài nhất.
6
b. Vali (B)
8
c. Biến đổi xâu
10
3. Một số ví dụ cụ thể 
13
a. Bài toán 1: Tính hệ số nhị thức
13
b. Bài toán 2: Số Fibonacci
14
c. Bài toán 3: Mật khẩu (Đề thi HSG cấp tỉnh năm học 2015-2016-tỉnh Thanh Hóa)
16
d. Bài toán 4:Dãy con (Đề thi HSG cấp tỉnh năm học 2015-2016, tỉnh Thanh Hóa)
17
IV. Kết luận và đề xuất.
18
I. Mở đầu
1. Lý do chọn đề tài
Một trong các mục tiêu khi đưa Tin học vào trường học là nhằm giúp cho học sinh có khả năng phân tích, tổng hợp, trừu tượng hóa, khái quát hóa vấn đề và đặc biệt là phát triển tư duy. Muốn vậy ngoài dạy đại trà Tin học trong nhà trường nhằm đảm bảo tính phổ thông, hướng nghiệp và dạy nghề thì cần phải tạo điều kiện cho những học sinh có năng khiếu tin học được phát triển về khả năng lập trình và giải quyết các bài toán. Để đáp ứng yêu cầu này cần phải cung cấp cho học sinh những kiến thức về thuật toán và các phương pháp thiết kết thuật toán.
Thuật toán (Algorithm) là một trong những khái niệm quan trọng trong tin học. Có thể định nghĩa không hình thức về thuật toán như sau: Thuật toán là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán hoặc hành động cần thực hiện để giải quyết một vấn đề.
Mặc dù không tồn tại một phương pháp vạn năng có thể giúp ta thiết kế được thuật toán giải quyết mọi vấn đề, nhưng các nhà nghiên cứu đã tìm ra một số phương pháp thiết kế thuật toán cơ bản, các phương pháp này gọi là chiến lược thiết kế thuật toán. Mỗi phương pháp này có thể áp dụng để giải quyết một phạm vi khá rộng các bài toán.
Các phương pháp chung
Kỹ thuật Top-Down: Là kỹ thuật từ trên xuống giải các bài toán con nhận được trong qúa trình chia nhỏ một cách độc lập rồi kết hợp nghiệm của bài toán con ta nhận được nghiệm của bài toán lớn. Tuy nhiên quá trình phân chia ta gặp rất nhiều lần cùng một bài toán con. Giải quyết bằng kỹ thuật trên ta phải tính lại nhiều lần cùng một bài toán. Kỹ thuật nhận được sẽ kém hiệu quả.
Kỹ thuật Bottom-Up: Là kỹ thuật từ dưới lên. Xuất phát từ những trường hợp riêng đơn giản của bài toán thường là thấy nghiệm của chúng. Sau đó kết hợp nghiệm của chúng ta được những bài toán cỡ lớn hơn. Rồi lại kết hợp nghiệm của bài toán ta được bài toán con cỡ lớn hơn nữa và tiếp tục cho đến khi nhận được nghiệm của bài toán đã cho.
Phương pháp riêng
Chia để trị (divide-and-conquer), phương pháp tham ăn (Greedy-methor), Quay lui(Backtracking), quy hoạch động (dynamic programing), nhánh và cận (branch-and-bound)
Trong chương trình giảng dạy đại trà môn tin học ở trường THPT, phần thuật toán đã được đưa vào giảng dạy ở lớp 10 với tổng số tiết là 10. Với thời lượng học như thế học sinh có thể biết được khái niệm về thật toán, một số thuật toán giải các bài toán đơn giản. Tuy nhiên đối với những học sinh tham gia thi học sinh giỏi cấp tỉnh thì lượng kiến thức về thuật toán như thế là không đủ và cần phải cung cấp thêm các phương pháp về thiết kế thuật toán. Vì vậy đây là lý do tôi chọn đề tài “Sử dụng phương pháp quy hoạch động trong bồi dưỡng học sinh giỏi cấp tỉnh môn Tin học.”
2. Mục đích nghiên cứu.
Thông qua đề tài cung cấp thêm một phương pháp tư duy, tiếp cận để giải các bài toán trong bồi dưỡng HSG cấp tỉnh.
Đưa ra những bài toán quy hoạch động điển hình đã từng xuất hiện trong các kỳ thi HSG cấp tỉnh.
II. Nội dung
1. Cơ sở lý luận
a. Phương pháp quy hoạch động
 Tư tưởng của phương pháp
Phương pháp qui hoạch động cùng nguyên lý tối ưu được R.Bellman đề xuất vào những năm 50 của thế kỷ 20. Phương pháp này được áp dụng để giải một số bài toán như tổ chức sản xuất, kế hoạch hóa kinh tế
Trong ngành khoa học máy tính, quy hoạch động là một phương pháp giảm thời gian chạy của các thuật toán thể hiện các tính chất của các bài toán con gối nhau (overlapping substructure) và cấu trúc con tối ưu (optimail substructure) 
Cấu trúc con tối ưu có nghĩa là các lời giải tối ưu cho các bài toán con có thể được sử dụng để tìm các lời giải tối ưu cho các bài toán toàn cục. Có thể giải một bài toán với cấu trúc con tối ưu bằng một quy trình ba bước:
Bước 1: Chia bài toán thành các bài toán con nhỏ hơn.
Bước 2: Giải các bài toán này một các tối ưu bằng cách sử dụng đệ quy quy trình ba bước này.
Bước 3: Sử dụng các kết quả tối ưu để xây dựng một lời giải tối ưu cho bài toán ban đầu.
Các bài toán con được giải bằng cách chia chúng thành các bài toán nhỏ hơn, và cứ tiếp tục như thế, cho đến khi ta đến được trường hợp đơn giản dễ tìm lời giải.
Nói rằng một bài toán có các bài toán con trùng nhau nghĩa là một bài toán con đó được sử dụng để giải nhiều bài toán lớn hơn khác nhau. Ví dụ trong dãy Fibonacci, F3=F1+F2 và F4=F2+F3 khi tính mỗi số đều phải tính F2. Vì tính F5 cần đến cả F3 và F4. Như vậy tính F5 có thể tính F2 hai lần hoặc nhiều hơn. Điều này áp dụng mỗi khi có các bài toán con gối nhau: một cách tiếp cận ngây thơ có thể tốn thời gian tính toán lại lời giải tối ưu cho các bài toán con mà nó đã giải.
Để tránh việc đó, ta lưu trữ lời giải của các bài toán con đã giải. Do vậy nếu sau này ta cần giải lại chính bài toán đó, ta có thể lấy và sử dụng kết quả đã được tính toán. Hướng tiếp cận này được gọi là lưu trữ. Nếu ta chắc chắn một lời giải nào đó không còn cần thiết nữa, ta có thể xóa nó đi để tiết kiệm không gian bộ nhớ. Trong một số trường hợp, ta còn có thể tính lời giải cho các bài toán con mà ta biết trước rằng sẽ cần đến.
Quy hoạch động là kỹ thuật từ dưới lên (Bottom-Up). Chúng ta xuất phát từ những trường hợp riêng đơn giản nhất thường là thấy nghiệm ngay của của chúng. Sau đó kết hợp nghiệm của chúng ta được nghiệm của bài toán con cỡ lớn hơn. Rồi lại kết hợp nghiệm của các bài toán con này để nhận được nghiệm của bài toán lớn hơn nữa, và cứ tiếp tục cho đến khi nhận được nghiệm của bài toán đã cho. Như vậy tư tưởng cơ bản của phương pháp quy hoạch động là quá trình đi từ dưới lên, quá trình này ta sử dụng một bản để lưu trữ lời giải của bài toán con đã giải. Khi giải một bài toán con cần đến nghiệm của bài toán cỡ nhỏ hơn ta chỉ cần tìm trong bảng không phải giải lại. Như vậy nguyên lý “chia để trị” được đẩy tới cao độ ở đây.
b. Các bước thực hiện quy hoạch động.
* Bài toán tối ưu.
Trong thực tế ta thường gặp một số bài toán tối ưu loại sau: Có một đại lượng f hình thành trong một quá trình gồm nhiều giai đoạn mà ta chỉ quan tâm đến kết quả cuối cùng là trị của f phải lớn nhất hoặc nhỏ nhất. Ta gọi chung là giá trị tối ưu của f. Giá trị của f phụ thuộc vào những đại lượng xuất hiện trong bài toán mà mỗi bộ giá trị của chúng được gọi là trạng thái của hệ thống và cũng phụ thuộc vào cách thức đạt được giái trị f trong từng giai đoạn mà mỗi cách thức được gọi là một điều khiển. Đại lượng f thường được gọi là hàm mục tiêu và quá trình đạt được giá trị tối ưu của f được gọi là quá trình điều khiển tối ưu.
Ý tưởng cơ bản của nguyên lý tối ưu do R. Bellman đề xuất như sau: Với mỗi quá trình điều khiển tối ưu, đối với trạng thái bắt đầu A0, với mọi trạng thái A trong quá trình đó, phần quá trình kể từ trạng thái xem như trạng thái bắt đầu cũng là tối ưu.
Phương pháp tìm điều khiển tối ưu theo nguyên lý Bellman thường được gọi là quy hoạch động.
* Các bước thực hiện quy hoạch động.
Bước 1: Lập hệ thức
Dựa vào nguyên lý tối ưu tìm cách chia quá trình giải bài toán thành từng giai đoạn, sau đó tìm hệ thức biểu diễn tương quan quyết định của bước đang xử lý với các bước đã xử lý trước đó. Hoặc tìm cách phân rã bài toán thành các bài toán con tương tự có kích thước nhỏ hơn, tìm hệ thức nêu quan hệ giữa kết quả bài toán kích thước đã cho với các kết quả của các bài toán con cùng kiểu có kích thước nhỏ hơn của nó nhằm xây dựng phương trình truy toán (dạng hàm hoặc thủ tục đệ quy).
Cách xây dựng phương trình truy toán:
Chia việc giải bài toán thành n giai đoạn. Mỗi giai đoạn i có trạng thái ban đầu là t(i) và chịu tác động đều khiển là d(i) sẽ biến trạng thái tiếp theo t(i+1) của giai đoạn i+1 (i=1,2,n-1). Theo nguyên lý tối ưu của Bellman thì việc tối ưu giai đoạn cuối cùng không làm ảnh hưởng đến kết quả toàn bài toán. Với trạng thái ban đầu là t(n), sau khi làm giai đoạn n tốt nhất ta có trạng thái của giai đoạn n-1 là t(n-1) và tác động điều khiển của giai đoạn n-1 là d(n-1), có thể tiếp tục xét đến giai đoạn n-1. Sau khi tối ưu giai đoạn n-1 ta lại có t(n-2) và d(n-2) và có thể tối ưu giai đoạn n-2cho đến khi các giai đoạn từ n giảm đến 1 được tối ưu thì coi như hoàn thành bài toán. Gọi giá trị tối ưu của bài toán tính đến giai đoạn k là Fk, giá trị tối ưu của bài toán tính riêng ở giai đoạn k là Gk thì Fk=Fk-1+Gk hay :
"d
Fk(t(k))=max{Gk(t(k),d(k))+Fk-1(t(k-1))} (*)
Bước 2: Tổ chức dữ liệu và chương trình
Các giá trị của Fk trường được lưu trữ trong một bảng (mảng một chiều hoặc hai, ba chiều)
Cần lưu ý khởi tạo các giá trị ban đầucủa bảng cho thích hợp, đó là các kết quả của bài toán con có kích thước nhỏ nhất của bài toán đang giải.
F1(t(1))= max{G1(t(1),d(1))+F0(t(0))}
"d
Dựa vào phương trình truy toán (*) và các giái trị đã có trong bảng để tìm dần các giá trị còn lại của bảng.
Ngoài ra còn cần mảng lưu trữ nghiệm tương ứng với giái trị tối ưu trong từng giai đoạn.
Dựa vào bảng lưu trữ nghiệm và bảng giá trị tối ưu từng giai đoạn đã xây dựng, tìm ra kết quả bài toán.
Lưu ý: Làm tốt thuật toán bằng cách thu gọn hệ thức (*) và giảm kích thước miền nhớ. Thường tìm cách dùng mảng một chiều thay cho mảng hai chiều nếu giá trị một dòng (hoặc cột) của mảng hai chiều chỉ phụ thuộc một dòng (hoặc cột) kề trước.
c. Hạn chế của quy hoạch động
Việc tìm công thức, phương trình truy toán hoặc tìm cách phân rã bài toán nhiều khi đòi hỏi sự phân tích tổng hợp rất công phu, dễ sai sót, khó nhận ra như thế nào là thích hợp, đòi hỏi nhiều thời gian suy nghĩ. Đồng thời không phải lúc nào kết hợp lời giải của các bài toán con cũng cho kết quả của bài toán lớn hơn.
Số lượng các bài toán con cần giải quyết và lưu trữ kết quả có thể rất lớn, không thể chấp nhận được.
Không phải bài toán tối ưu nào cũng có thể giải bằng phương pháp qui hoạch động.
2. Một số bài toán quy hoạch động điển hình.
a. Dãy con đơn điệu dài nhất.
 Mô hình
Cho dãy a1 ,a2,an. Hãy tìm một dãy con tăng có nhiều phần tử nhất của dãy.
Đặc trưng của bài toán này là:
Các phần tử trong dãy kết quả chỉ xuất hiện 1 lần. Vì vậy phương pháp làm là ta sẽ dùng vòng lặp For duyệt qua các phần tử ai trong dãy, các phần tử trong dãy có thể được chọn nhiều lần nên ta thực hiện bằng phương pháp cho giá trị cần quy đổi tăng dần từng đơn vị.
Thứ tự của các phần tử được chọn phải giữ nguyên so với dãy ban đầu.
Đặc trưng này có thể mất đi trong một số bài toán khác tùy vào yêu cầu cụ thể. Chẳng hạn bài Tam giác bằng nhau.
 Công thức QHĐ
Hàm mục tiêu f=độ dài dãy con.
Vì độ dài dãy con chỉ phụ thuộc vào 1 yếu tố là dãy ban đầu nên bảng phương án là bảng một chiều. Gọi L(i) là độ dài dãy con tăng dài nhất, các phần tử lấy trong miền từ a1 đến ai và phần tử cuối cùng là ai.
Nhận xét với cách làm này ta đã chia 1 bài toán lớn (dãy con của n số) thành các bài toán con cùng kiểu có kích thước nhỏ hơn (dãy con của dãy i số). Vấn đề là công thức truy hồi để phối hợp kết quả của các bài toán con.
Ta có công thức quy hoạch động để tính L(i) như sau:
L(1)=1. (Hiển nhiên)
L(i)=Max(1, L(j)+1 với mọi phần tử j: 0<j<i và aj ≤ai).
Tính L(i): phần tử đang được xét là ai. Ta tìm đến phần tử aj<ai có L(j) lớn nhất. Khi đó nếu bổ sung ai vào sau dãy conaj ta sẽ được dãy con tăng dần dài nhất xét từ a1ai.
 Cài đặt
Bảng phương án là một mảng một chiều L để lưu giữ các giá trị của hàm QHĐ L(i). Đoạn chương trình tính các giá trị của mảng L như sau:
For i:=1 to n do
Begin
	L[i]:=1;
	For j:=1 to i-1 do
	If (a[j]<=a[i]) and L[i]<L[j]+1 then
	L[i]:=L[j]+1;
End;
Như vậy chi phí không gian của bài toán là O(n), chi phí thời gian là O(n2). Có một số phương pháp cài đặt tốt hơn so với phương pháp trên, cho chi phí thời gian là O(nlogn).
 Một số bài toán biến thể.
Bài toán dãy con đơn điệu dài nhất có biến thể đơn giản nhất là bài toán dãy con đơn điệu giảm dài nhất, tuy nhiên chúng ta có thể coi chúng như là một. Sau đây là một số bài toán khác.
Bài toán 1: bố trí phòng họp (mất tính thứ tự so với dãy ban đầu)
Có n cuộc họp, cuộc họp thứ i bắt đầu vào thời điểm ai và kết thúc ở thời điểm bi. Do chỉ có một phòng hội thảo nên 2 cuộc họp bất kỳ sẽ cùng được bố trí phục vụ nếu khoảng thời gian làm việc của chúng chỉ giao nhau tại đầu mút. Hãy bố trí phòng họp để phục vụ được nhiều cuộc họp nhất.
Hướng dẫn: sắp xếp các cuộc họp tăng dần theo thời điểm kết thúc bi. Cuộc họp i sẽ bố trí được sau cuộc họp j nếu và chỉ nếu j<i và bj≤ai. Yêu cầu bố trí được nhiều cuộc họp nhất có thể đưa về việc tìm dãy các cuộc họp dài nhất thỏa mãn điều kiện trên.
Bài toán 2: Cho thuê máy
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 i muốn dử dụng máy trong khoảng thời gian từ ai đến bi và trả tiền thuê là ci. 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 hai 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ê).
Tương tự như bài toán 1 nếu sắp xếp các đơn hàng theo thời điểm kết thúc, ta sẽ đưa được bài toán 2 về bài toán tìm dãy con có tổng lớn nhất. Bài toán này là biến thể của bài toán tìm dãy con tăng dài nhất, ta có thể cài đặt bằng đoạn chương trình sau:
For i:=1 to n do
Begin
	L[i]:=c[i];
	For j:=1 to i-1 do
	If (b[j]<=a[i]) and L[i]<L[j]+c[i] then
	L[i]:=L[j]+c[i];
End;
Bài toán 3: Dãy tam giác bao nhau
Cho n tam giác trên mặt phẳng. Tam giác i bao tam giác j nếu 3 đỉnh của tam giác j đều nằm trong tam giác i (có thể nằm trên cạnh). Hãy tìm dãy tam giác bao nhau có nhiều tam giác nhất.
Hướng dẫn: sắp xếp các tam giác tăng dần về diện tích. Khi đó tam giác i sẽ bao tam giác j nếu j<i và 3 đỉnh của j nằm trong i. Từ đó có thể đưa về bài toán tìm dãy tăng dài nhất.
Việc kiểm tra điểm M có nằm trong tam giác ABC không có thể dựa trên phương pháp tính diện tích: Điểm M nằm trong tam giác nếu S(ABC)=S(ABM)+S(ACM)+S(BCM). Bài toán có một số biến thể khác như tìm dãy hình tam giác, hình chữ nhật bao nhau có tổng diện tích lớn nhất.
Bài toán 4: Dãy WAVIO
Dãy số WAVIO là dãy số nguyên thỏa mãn các tính chất: các phần tử đầu sắp xếp thành một dãy tăng dần đến một phần tử đỉnh sau đó giảm dần. Ví dụ dãy số 1 2 3 4 5 2 1 là một dãy WAVIO có độ dài 7. Cho một dãy gồm N số nguyên, hãy chỉ ra một dãy con WAVIO có độ dài lớn nhất trích ra từ dãy đó.
Hướng dẫn: L1[i] là mảng ghi độ dài lớn nhất của một dãy con tăng dần trích ra từ dãy N phần tử kể từ phần tử 1 đến phần tử ai.
L2[i]: mảng ghi độ dài lớn nhất của dãy con giảm dần trích ra từ dãy N phần tử kể từ phần phần tử aN đến ai. Ta tìm phần tử j trong 2 mảng L1, L2 thỏa mãn L1[j]+L2[j] lớn nhất.
b. Vali (B)
Mô hình
Có n đồ vật, vật thứ i có trong lượng ai và giá trị bi. Hãy chọn ra một số các đồ vật, mỗi vật một cái để xếp vào một va li có trọng lượng tối đa W sao cho tổng các giá trị của vali là lớn nhất.
Công thức
Hàm mục tiêu f: tổng giá trị của vali.
Nhận xét: giá trị của vali phụ thuộc vào 2 yếu tố: Có bao nhiêu vật đang xét và trọng lượng của các vật. Do đó bảng phương án sẽ là mảng hai chiều.
L[i,j]: Tổng giá trị lớn nhất của vali khi xét từ vật 1đến vật i và trọng lượng của vali chưa vượt quá j. Chú ý rằng khi xét đến L[i,j] thì các giá trị trên bảng phương án đều đã được tối ưu.
Tính L[i,j]: vật đang xét là ai với trọng lượng của vali không vượt quá j. Có 2 khả năng xảy ra:
Nếu chọn ai đưa vào vali, trọng lượng vali trước đó phải nhỏ hơn hoặc bằng j-a[i]. Vì mỗi vật chỉ được chọn 1 lần nên giá trị lớn nhất của vali lúc đó là L[i-1,j-a[i])+b[i].
Nếu không chọn ai, trọng lượng của vali là như cũ (như lúc trước khi chọn ai): L[i,j]
Ta có L[i,j]=max(L[i-1,j-a[i]],+b[i],L[i-1,j]).
Cài đặt
For i:=1 to n do
For j:=1 to W do
	If (b[j]<=j then
	L[i,j]:= max(L[i-1,j-a[i]],+b[i],L[i-1,j])
	Else L[i,j]:=L[i-1,j];
Một số bài toán biến thể.
Bài toán 1:Dãy con có tổng bằng S.
Cho dãy a1 ,a2,an.Tìm một dãy con của dãy đó có tổng bằng S.
Hướng dẫn
Đặt L[i,t]=1 nếu có thể tạo ra tổng t từ một dãy con của dãy gồm các phần tử a1 ,a2,ai. ngược lại thì L[i,t]=0. Nếu L[n,S]=1 thì đáp án của bài toán là có. Ta có thể tính L[i,t] theo công thức L[i,t]=1 nếu L[i,t]=1 hoặc L[i-1,t-a[i]=1
Cài đặt
Nếu áp dụng công thức trên thì ta cần dùng bảng phương án hai chiều. Ta có nhận xét rằng để tính dòng thứ i, ta chỉ cần dòng i-1. Bảng phương án khi đó chỉ cần một mảng một chiều L[0..S] và được tính như sau:
L[t]:=0; L[0]:=1;
For i:=1 to ndo
	For t:=S downto a[i] do
	If (L[t]=0) and L[t-a[i]=1 then L[t]:=1
Dễ thấy chi phí không gian của cách cài đặt trên là O(m), chi phí thời gian là O(m.n), với m là tổng của n số.
Bài toán 2: Chia kẹo
Cho n gói kẹo, gói thứ i có ai viên. Hãy chia các gói thành i phần sao cho chênh lệnh giữa hai phần là ít nhất.
Hướng dẫn: Gọi T là tổng số kẹo của n gói. Chúng ta cần tìm số S lớn nhất thỏa mãn:
S≤T/2 và có một dãy con của dãy a có tổng bằng S.
Khi đó sẽ có cách chia với chênh lệnh 2 phần là T-2S là nhỏ nhất và dãy con có tổng bằng S ở trên gồm các phần tử là các gói kẹo thuộc phần thứ nhất. Phần thứ hai là các gói kẹo còn lại.
Bài toán 3: Điền dấu
Cho n số tự nhiên a1 ,a2,an. Ban đầu các số được đặt liên tiếp theo đúng thứ tự cách nhau bởi dấu ?: a1?a2??an. 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 có giá trị là S không.
Hướng dẫn: Đặt L(i,t)=1 nếu có thể điền dấu vào i số đầu tiên và cho kết quả bằng t. Ta có công thức sau để tính L:
L(1,a[1])=1
L(i,t)=1 nếu L(i-1, t+a[i])=1 hoặc L[i-1,t-a[i])=1.
Nếu L(n,S)=1thì đáp án của bài toán là có. Khi cài đặt có thể dùng một mảng hai chiều (lưu toàn bộ bảng phương án) hoặc hai mảng một chiều (để lưu dòng i và dòng i-1). Chú ý là chỉ số theo t của mảng phải có cả phần âm (tức là từ -T đến T, với T là tổng của n số), vì trong này dùng dấu – nên có thể tạo ra các tổng âm. Bài này có một biến thể và đặt dấu sao cho kết quả là một số chia hết cho k. Ta có thuật giải tương tự như bài toán trên bằng cách thay các phép cộng, trừ bằng các phép cộng, trừ theo môđun k và dùng mảng đánh dấu với các giá trị từ 0 đến k-1(là các số dư có thể có khi chia cho k). Đáp án của bài toán là L(n,0).
c. Biến đổi xâu
 Mô hình
Cho hai xâu X,F. Xâu nguồn có n kí tự X1 X2Xn. Xâu đích có m kí tự F1F2Fm. Có 3 phép biến đổi
- Chèn một kí tự vào sau kí tự thứ i: I i C
- Thay thế kí tự ở vị trí i bằng kí tự C: R iC.
- Xóa kí tự ở vị trí thứ i: D 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
 Hướng dẫn:
Hàm mục tiêu f: số phép biến đổi
Dễ thấy số phép biến đổi phụ thuộc vào vị trí i đang xét của xâu X và vị trí j đang xét của xâu F. Do vậy để cài đặt cho bảng phương án ta sẽ dùng mảng hai chiều
Gọi L(i,j) là số phép biến đổi ít nhất để biến xâu X(i) gồm i kí tự phần đầu của X (X(i)=X[1..i]) thành xâu F(j) gồm j kí tự phần đầu của F (F(j)=F[1..j]). Dễ thấy F(0,j)=j và F(i,0) =i
Có hai trường hợp xảy ra
Nếu X[i]=F[j] thì hai xâu trên có dạng X1 X2Xi-1Xi và F1F2Fj-1Xi. Lúc này