Bỏ qua điều hướng, tới nội dung chính
Học C
Bài 28.332 phút đọc

Quy hoạch động

Sau bài này bạn sẽ làm được

  • Nhận ra bài toán con chồng lấn
  • Chuyển đệ quy có nhớ sang bảng
  • Cài knapsack 0/1, dãy con chung dài nhất và khoảng cách sửa
  • Giảm bảng hai chiều xuống một chiều

Quy hoạch động là chia để trị cộng thêm một cuốn sổ ghi lại kết quả đã tính. Chỉ vậy thôi, nhưng nó biến hàng loạt bài toán từ mũ thành đa thức, và nhận ra khi nào dùng được là kỹ năng quan trọng nhất.

#Hai dấu hiệu nhận ra

Bài toán con chồng lấn
Cùng một bài toán con xuất hiện nhiều lần trong cây đệ quy. Đây là dấu hiệu phân biệt quy hoạch động với chia để trị: ở chia để trị các bài toán con hoàn toàn độc lập nên không lặp lại.
Cấu trúc con tối ưu
Lời giải tối ưu của bài toán dựng được từ lời giải tối ưu của các bài toán con. Điều kiện này chung với tham lam ở Bài 28.2.
/* Fibonacci: bai toan con chong lan rat ro

     fib(5)
     |
     +-- fib(4)
     |   +-- fib(3)        <- lan 1
     |   |   +-- fib(2)
     |   |   +-- fib(1)
     |   +-- fib(2)        <- lan 1
     +-- fib(3)            <- lan 2, tinh lai TU DAU
         +-- fib(2)        <- lan 2
         +-- fib(1)

   Voi n = 40: 331160281 loi goi, trong khi chi co 41 gia tri khac nhau. */
Chia để trịQuy hoạch động
Bài toán conĐộc lậpChồng lấn
Có lưu kết quả khôngKhông cầnBắt buộc
Ví dụMerge sort, tìm nhị phânFibonacci, knapsack, LCS
Bộ nhớ phụThường O(log n)Thường O(n) hoặc O(n bình phương)

#Từ trên xuống và từ dưới lên

hai-huong.c
#include <stdlib.h>
#include <string.h>

/* Cách 1: TỪ TRÊN XUỐNG, đệ quy có nhớ.
   Giữ nguyên công thức truy hồi, chỉ thêm bảng nhớ. */
static long long fib_memo(int n, long long *nho)
{
    if (n <= 1) return n;

    if (nho[n] >= 0) return nho[n];      /* đã tính rồi */

    return nho[n] = fib_memo(n - 1, nho) + fib_memo(n - 2, nho);
}

long long fib_tren_xuong(int n)
{
    if (n < 0) return -1;

    long long *nho = malloc((size_t)(n + 1) * sizeof *nho);

    if (nho == NULL) return -1;

    for (int i = 0; i <= n; ++i) nho[i] = -1;

    long long kq = fib_memo(n, nho);

    free(nho);

    return kq;
}

/* Cách 2: TỪ DƯỚI LÊN, điền bảng bằng vòng lặp.
   Phải tự xác định thứ tự tính. */
long long fib_duoi_len(int n)
{
    if (n <= 1) return n;

    long long a = 0, b = 1;

    for (int i = 2; i <= n; ++i) {
        long long t = a + b;

        a = b;
        b = t;
    }

    return b;      /* O(n) thời gian, O(1) bộ nhớ */
}
Từ trên xuốngTừ dưới lên
Viết từ công thức truy hồiTrực tiếp, gần như chép lạiPhải nghĩ thứ tự tính
Chỉ tính bài toán con cần thiếtCóKhông, tính hết
Chi phí gọi hàmCó, mỗi ô một lời gọiKhông
Tràn ngăn xếpCó thể, độ sâu bằng số trạng tháiKhông bao giờ
Giảm bộ nhớ được khôngKhóDễ, thường xuống một chiều
Tốc độChậm hơn 2 tới 3 lầnNhanh hơn
terminal
./do-hai-huong 90
fib de quy thuan  : khong doi noi (O(1.618^n))
fib tren xuong    : 0.000012 s
fib duoi len      : 0.000001 s

voi bang 10000 x 10000:
  tren xuong : 2.412 s, 800 MB (bang + ngan xep)
  duoi len   : 0.884 s, 800 MB
  duoi len 1 chieu : 0.812 s, 80 KB

#Năm bước giải một bài quy hoạch động

  1. Xác định trạng thái

    dp[i] hoặc dp[i][j] nghĩa là gì. Đây là bước khó nhất và quan trọng nhất. Viết định nghĩa ra thành một câu tiếng Việt đầy đủ trước khi viết mã.

  2. Viết công thức truy hồi

    dp[i] tính từ những ô nào. Thường có dạng lấy nhỏ nhất, lớn nhất hoặc tổng trên các lựa chọn.

  3. Xác định điều kiện cơ sở

    Những ô nào biết ngay không cần tính. Thường là hàng 0 và cột 0 của bảng.

  4. Xác định thứ tự tính

    Khi tính dp[i] thì mọi ô nó phụ thuộc phải đã có. Với bảng hai chiều thường là duyệt theo hàng từ trên xuống, trong mỗi hàng từ trái sang phải.

  5. Tối ưu bộ nhớ

    Nếu dp[i] chỉ phụ thuộc dp[i-1] thì giữ hai hàng là đủ, hoặc thậm chí một hàng. Xem mục cuối bài.

Ví dụ áp dụng: dãy con tăng dài nhất

lis.c
#include <stdlib.h>

/* Buoc 1: dp[i] = do dai day con tang dai nhat KET THUC TAI i
   Buoc 2: dp[i] = 1 + max{ dp[j] : j < i va a[j] < a[i] }
   Buoc 3: dp[i] = 1 khi khong co j nao thoa
   Buoc 4: tinh i tu 0 den n-1, vi dp[i] chi phu thuoc j < i
   Buoc 5: khong giam duoc, vi dp[i] phu thuoc MOI j truoc no    */
int lis(const int *a, size_t n)
{
    if (n == 0) return 0;

    int *dp = malloc(n * sizeof *dp);

    if (dp == NULL) return -1;

    int tot_nhat = 1;

    for (size_t i = 0; i < n; ++i) {
        dp[i] = 1;

        for (size_t j = 0; j < i; ++j)
            if (a[j] < a[i] && dp[j] + 1 > dp[i])
                dp[i] = dp[j] + 1;

        if (dp[i] > tot_nhat) tot_nhat = dp[i];
    }

    free(dp);

    return tot_nhat;      /* KHONG phai dp[n-1] */
}
terminal
gcc -std=c17 -Wall -Wextra lis.c main.c -o t && ./t
mang : 10 9 2 5 3 7 101 18
dp   :  1 1 1 2 2 3   4  4
ket qua: 4   (vi du 2 3 7 101 hoac 2 3 7 18)

#Knapsack 0/1

Có n món, món thứ i nặng w[i] và có giá trị v[i]. Ba lô chịu được tối đa W. Mỗi món lấy hoặc không lấy, không cắt được. Tổng giá trị lớn nhất là bao nhiêu.

knapsack.c
#include <stdlib.h>
#include <string.h>

/* Buoc 1: dp[i][j] = gia tri lon nhat khi xet i mon dau tien
                      va suc chua con lai la j
   Buoc 2: dp[i][j] = max( dp[i-1][j],                  khong lay mon i-1
                           dp[i-1][j - w[i-1]] + v[i-1] lay mon i-1 )
   Buoc 3: dp[0][j] = 0 voi moi j
   Buoc 4: tinh i tang dan, moi i tinh j bat ky            */
int knapsack_2d(int W, const int *w, const int *v, int n)
{
    if (W < 0 || n < 0) return -1;

    int **dp = malloc((size_t)(n + 1) * sizeof *dp);

    if (dp == NULL) return -1;

    for (int i = 0; i <= n; ++i) {
        dp[i] = calloc((size_t)(W + 1), sizeof *dp[i]);

        if (dp[i] == NULL) {
            for (int k = 0; k < i; ++k) free(dp[k]);

            free(dp);

            return -1;
        }
    }

    for (int i = 1; i <= n; ++i)
        for (int j = 0; j <= W; ++j) {
            dp[i][j] = dp[i - 1][j];                       /* khong lay */

            if (w[i - 1] <= j) {
                int lay = dp[i - 1][j - w[i - 1]] + v[i - 1];

                if (lay > dp[i][j]) dp[i][j] = lay;        /* lay */
            }
        }

    int kq = dp[n][W];

    for (int i = 0; i <= n; ++i) free(dp[i]);

    free(dp);

    return kq;
}

Bản một chiều, duyệt ngược

knapsack-1d.c
/* dp[i] chi phu thuoc dp[i-1], nen giu MOT hang la du.
   Nhung phai duyet j NGUOC, va day la diem mau chot. */
int knapsack(int W, const int *w, const int *v, int n)
{
    if (W < 0 || n < 0) return -1;

    int *dp = calloc((size_t)(W + 1), sizeof *dp);

    if (dp == NULL) return -1;

    for (int i = 0; i < n; ++i)
        for (int j = W; j >= w[i]; --j)      /* NGUOC, tu W xuong w[i] */
            if (dp[j - w[i]] + v[i] > dp[j])
                dp[j] = dp[j - w[i]] + v[i];

    int kq = dp[W];

    free(dp);

    return kq;
}
Bảng hai chiềuBảng một chiều
Bộ nhớO(n nhân W)O(W)
Với n = 1000, W = 100000400 MB400 KB
Truy vết được món nào đã lấyCóKhông, phải lưu thêm
Tốc độChuẩnNhanh hơn, vừa bộ nhớ đệm hơn

#Dãy con chung dài nhất

Ô tô đậm là nơi hai ký tự bằng nhau, giá trị lấy từ ô chéo trên trái cộng một. Ô còn lại lấy lớn nhất của ô trên và ô trái.
lcs.c
#include <stdlib.h>
#include <string.h>

/* Buoc 1: dp[i][j] = do dai day con chung dai nhat cua
                      a[0..i) va b[0..j)
   Buoc 2: neu a[i-1] == b[j-1]:  dp[i][j] = dp[i-1][j-1] + 1
           nguoc lai:             dp[i][j] = max(dp[i-1][j], dp[i][j-1])
   Buoc 3: dp[0][j] = dp[i][0] = 0
   Buoc 4: i tang dan, moi i thi j tang dan               */
int lcs(const char *a, const char *b)
{
    size_t m = strlen(a), n = strlen(b);

    /* Mot mang phang (m+1) x (n+1), truy cap bang dp[i * (n+1) + j] */
    int *dp = calloc((m + 1) * (n + 1), sizeof *dp);

    if (dp == NULL) return -1;

    for (size_t i = 1; i <= m; ++i)
        for (size_t j = 1; j <= n; ++j) {
            if (a[i - 1] == b[j - 1])
                dp[i * (n + 1) + j] = dp[(i - 1) * (n + 1) + (j - 1)] + 1;
            else {
                int tren = dp[(i - 1) * (n + 1) + j];
                int trai = dp[i * (n + 1) + (j - 1)];

                dp[i * (n + 1) + j] = (tren > trai) ? tren : trai;
            }
        }

    int kq = dp[m * (n + 1) + n];

    free(dp);

    return kq;
}
terminal
gcc -std=c17 -Wall -Wextra lcs.c main.c -o t && ./t ABCD ACBD
a = ABCD
b = ACBD

     -  A  C  B  D
  -  0  0  0  0  0
  A  0  1  1  1  1
  B  0  1  1  2  2
  C  0  1  2  2  2
  D  0  1  2  2  3

LCS = 3   (ABD hoac ACD)

#Khoảng cách sửa

Khoảng cách Levenshtein
Số phép sửa ít nhất để biến chuỗi này thành chuỗi kia, với ba phép được dùng: chèn một ký tự, xóa một ký tự, thay một ký tự.
edit.c
#include <stdlib.h>
#include <string.h>

static int nho_nhat_3(int a, int b, int c)
{
    int m = (a < b) ? a : b;

    return (m < c) ? m : c;
}

/* dp[i][j] = so phep sua it nhat de bien a[0..i) thanh b[0..j) */
int khoang_cach_sua(const char *a, const char *b)
{
    size_t m = strlen(a), n = strlen(b);

    int *dp = malloc((m + 1) * (n + 1) * sizeof *dp);

    if (dp == NULL) return -1;

    for (size_t i = 0; i <= m; ++i) dp[i * (n + 1)] = (int)i;   /* xoa het */
    for (size_t j = 0; j <= n; ++j) dp[j]           = (int)j;   /* chen het */

    for (size_t i = 1; i <= m; ++i)
        for (size_t j = 1; j <= n; ++j) {
            if (a[i - 1] == b[j - 1])
                dp[i * (n + 1) + j] = dp[(i - 1) * (n + 1) + (j - 1)];
            else
                dp[i * (n + 1) + j] = 1 + nho_nhat_3(
                    dp[(i - 1) * (n + 1) + j],          /* xoa a[i-1] */
                    dp[i * (n + 1) + (j - 1)],          /* chen b[j-1] */
                    dp[(i - 1) * (n + 1) + (j - 1)]);   /* thay a[i-1] bang b[j-1] */
        }

    int kq = dp[m * (n + 1) + n];

    free(dp);

    return kq;
}
terminal
gcc -std=c17 -Wall -Wextra edit.c main.c -o t && ./t kitten sitting
a = kitten
b = sitting

     -  s  i  t  t  i  n  g
  -  0  1  2  3  4  5  6  7
  k  1  1  2  3  4  5  6  7
  i  2  2  1  2  3  4  5  6
  t  3  3  2  1  2  3  4  5
  t  4  4  3  2  1  2  3  4
  e  5  5  4  3  2  2  3  4
  n  6  6  5  4  3  3  2  3

khoang cach = 3
  k -> s  (thay)
  e -> i  (thay)
  chen g  (chen)

#Giảm bảng hai chiều xuống một chiều

lcs-1d.c
/* dp[i][j] chi phu thuoc hang i-1 va o ben trai cung hang.
   Nen giu HAI hang la du: hang truoc va hang hien tai. */
int lcs_2_hang(const char *a, const char *b)
{
    size_t m = strlen(a), n = strlen(b);

    int *truoc = calloc(n + 1, sizeof *truoc);
    int *hien  = calloc(n + 1, sizeof *hien);

    if (truoc == NULL || hien == NULL) { free(truoc); free(hien); return -1; }

    for (size_t i = 1; i <= m; ++i) {
        for (size_t j = 1; j <= n; ++j)
            if (a[i - 1] == b[j - 1])
                hien[j] = truoc[j - 1] + 1;
            else
                hien[j] = (truoc[j] > hien[j - 1]) ? truoc[j] : hien[j - 1];

        /* Doi vai tro hai hang, khong chep du lieu */
        int *t = truoc;

        truoc = hien;
        hien  = t;

        memset(hien, 0, (n + 1) * sizeof *hien);
    }

    int kq = truoc[n];

    free(truoc);
    free(hien);

    return kq;
}

Xuống hẳn một hàng

lcs-1-hang.c
/* Chi giu MOT hang, nhung phai nho gia tri o cheo truoc khi ghi de. */
int lcs_1_hang(const char *a, const char *b)
{
    size_t m = strlen(a), n = strlen(b);

    int *dp = calloc(n + 1, sizeof *dp);

    if (dp == NULL) return -1;

    for (size_t i = 1; i <= m; ++i) {
        int cheo = 0;      /* dp[i-1][j-1] cua vong truoc */

        for (size_t j = 1; j <= n; ++j) {
            int tam = dp[j];      /* luu dp[i-1][j] TRUOC khi ghi de */

            if (a[i - 1] == b[j - 1])
                dp[j] = cheo + 1;
            else
                dp[j] = (dp[j] > dp[j - 1]) ? dp[j] : dp[j - 1];

            cheo = tam;           /* tam thanh dp[i-1][j-1] cho vong sau */
        }
    }

    int kq = dp[n];

    free(dp);

    return kq;
}
CáchBộ nhớm = n = 10000 tốnTruy vết được không
Bảng đầy đủO(m nhân n)400 MBCó
Hai hàngO(n)80 KBKhông
Một hàngO(n)40 KBKhông
Chia để trị HirschbergO(n)40 KBCó, nhưng tốn gấp đôi thời gian

Tự làm thử

  1. Cài Fibonacci theo cả ba cách và đo với n bằng 40, rồi tìm n làm bản đệ quy có nhớ tràn ngăn xếp.
  2. Cài dãy con tăng dài nhất bản O(n bình phương) và bản O(n log n), so kết quả trên một nghìn mảng ngẫu nhiên.
  3. Cài knapsack bản một chiều, đổi vòng lặp thành duyệt xuôi, và giải thích kết quả nhận được.
  4. Cài LCS kèm truy ngược để in ra dãy con chung, thử với ABCD và ACBD.
  5. Cài khoảng cách sửa và dùng nó tìm năm từ gần nhất trong một từ điển cho một từ gõ sai.

Trình chấm điểm tự động sẽ được bổ sung ở giai đoạn sau. Hiện tại bạn tự chạy thử trên máy.

Tóm tắt

  • Quy hoạch động cần hai điều kiện: bài toán con chồng lấn và cấu trúc con tối ưu.
  • Từ trên xuống viết thẳng từ công thức truy hồi và chỉ tính ô cần thiết. Từ dưới lên nhanh hơn và giảm bộ nhớ được.
  • Bước quan trọng nhất là định nghĩa trạng thái thành một câu đầy đủ. Định nghĩa mơ hồ thì công thức truy hồi chắc chắn sai.
  • Knapsack 0/1 bản một chiều phải duyệt sức chứa ngược. Duyệt xuôi biến nó thành bài knapsack không giới hạn.
  • Khi dp[i] chỉ phụ thuộc dp[i-1] thì giảm bảng xuống một hàng được, đổi lại mất khả năng truy vết.