Quy hoạch động
Ví dụ > Bàn cờ

Xét một bàn cờ hình vuông n × n và một hàm giá trị c(i, j) trả về giá trị của ô i,j (i là chỉ số hàng, j là chỉ số cột). Ví dụ: bàn cờ 5 × 5:
+---+---+---+---+---+
5 | 6 | 7 | 4 | 7 | 8 |
  +---|---|---|---|---+
4 | 7 | 6 | 1 | 1 | 4 |
  +---|---|---|---|---+
3 | 3 | 5 | 7 | 8 | 2 |
  +---|---|---|---|---+
2 | 2 | 6 | 7 | 0 | 2 |
  +---|---|---|---|---+
1 | 7 | 3 | 5 | 6 | 1 |
  +---+---+---+---+---+
    1   2   3   4   5
Trong ví dụ, ta có chẳng hạn c(1, 3) = 5
Giả sử ta có một quân cờ có thể xuất phát tại một ô bất kỳ tại hàng đầu tiên (hàng 1), và ta cần tìm đường đi ngắn nhất (tổng giá trị của các ô đi qua là nhỏ nhất) để tới được hàng cuối cùng (hàng n), với điều kiện quân cờ chỉ có thể tiến thẳng hoặc tiến theo đường chéo sang trái hoặc sang phải. Nghĩa là, một quân cờ tại ô (1,3) có thể nhảy sang được một trong ba ô (2,2), (2,3) và (2,4).
+---+---+---+---+---+
5 |   |   |   |   |   |
  +---|---|---|---|---+
4 |   |   |   |   |   |
  +---|---|---|---|---+
3 |   |   |   |   |   |
  +---|---|---|---|---+
2 |   | x | x | x |   |
  +---|---|---|---|---+
1 |   |   | O |   |   |
  +---+---+---+---+---+
    1   2   3   4   5
Bài toán này thể hiện tính chất cấu trúc con tối ưu. Nghĩa là, lời giải cho bài toán lớn phụ thuộc vào lời giải cho các bài toán con. Ta định nghĩa hàm q(i, j) như sau:
Nếu ta có thể tìm được giá trị của hàm này tại tất cả các ô nằm trên hàng n, ta sẽ chọn lấy giá trị nhỏ nhất và lần ngược con đường đó để có được đường đi ngắn nhất.
Dễ thấy rằng q(i, j) bằng chi phí tối thiểu để đến ô bất kỳ trong ba ô nằm dưới nó (do chỉ có thể đến được (i,j) từ các ô này) cộng thêm c(i, j). Ví dụ:
+---+---+---+---+---+
5 |   |   |   |   |   |
  +---|---|---|---|---+
4 |   |   | A |   |   |
  +---|---|---|---|---+
3 |   | B | C | D |   |
  +---|---|---|---|---+
2 |   |   |   |   |   |
  +---|---|---|---|---+
1 |   |   |   |   |   |
  +---+---+---+---+---+
    1   2   3   4   5
Bây giờ, ta định nghĩa q(i, j) một cách chính thức hơn:
Phương trình trên rất dễ hiểu. Dòng đầu tiên là các trường hợp đặc biệt, dòng này có mục đích dọn dẹp cho tính chất đệ quy. Dòng thứ hai mô tả những gì xảy ra tại hàng đầu tiên, để ta có xuất phát điểm. Dòng thứ ba, phần đệ quy, là phần quan trọng nhất. Về cơ bản, nó giống với ví dụ A,B,C,D.
Từ định nghĩa này, ta có thể dễ dàng tạo một đoạn mã đệ quy để tính q(i, j). Trong đoạn mã giả sau, n là kích thước của bàn cờ, c(i, j) là hàm chi phí, và min() trả về giá trị nhỏ nhất của các giá trị nằm trong ngoặc:
function minCost(i, j)
if j = 0 or j = n + 1
  return infinity
else if i = 1
  return c(i, j)
else  
  return min(minCost(i-1, j-1), minCost(i-1, j), minCost(i-1, j+1)) + c(i, j)
Cần lưu ý rằng hàm này chỉ tính chi phí của đường đi chứ không phải đường đi đích thực. Ta sẽ nói đến phần đó sau.
Cũng như ví dụ về dãy Fibonacci, hàm trên chạy rất rất lâu do nó phải tốn hàng núi thời gian để tính đi tính lại các đường đi ngắn nhất. Tuy nhiên, ta có thể tính nhanh hơn rất nhiều nếu hàm trên thực hiện công việc lưu trữ các giá trị đã được tính (trong một mảng). Hoặc, ta còn có thể nhanh hơn nữa nếu tính toán theo kiểu từ dưới lên và một mảng hai chiều q[i, j]. Tại sao? Đơn giản là vì khi đó ta tính toán mỗi đường đi chỉ một lần, và ta có thể chọn cái gì cần tính toán trước.
Ta còn cần biết đường đi thực sự như thế nào. Vấn đề đó có thể được giải quyết bằng cách sử dụng một mảng nữa: "mảng nút đứng trước" p[i, j]. Mảng này lưu các dấu vết về chuyện các đường đi từ hướng nào tới. Xét đoạn mã sau:
function computeShortestPathArrays()
for x from 1 to n
  q[1, x]:= c(1, x)

for y from 1 to n
  q[y, 0]:= infinity
  q[y, n + 1]:= infinity

for y from 2 to n
  for x from 1 to n
  m:= min(q[y-1, x-1], q[y-1, x], q[y-1, x+1])
  q[y, x]:= m + c(y, x)
  c[y, x]:= q[y, x]

  if m = q[y-1, x-1]
  p[y, x]:= -1
  else if m = q[y-1, x]
  p[y, x]:= 0
  else
  p[y, x]:= 1
Bây giờ, vấn đề đơn giản còn lại là xác định cực tiểu và in nó ra.
function computeShortestPath()
computeShortestPathArrays()

minIndex:= 1
min:= q[n, 1] 

for i from 2 to n 
  if q[n, i] < min
  minIndex:= i
  min:= q[n, i]

printPath(n, minIndex)

function printPath(y, x)
print(x)
print("<-")

if y = 2
  print(x + p[y, x])
else
  printPath(y-1, x + p[y, x])