1. Giải thuật đệ quy

Một bài toán khá quen thuộc là tính số tổ hợp chập k của n theo công thức truy hồi:

Công thức trên đã gợi ý cho chúng ta một giải thuật đệ quy như sau:

int Comb(int n, int k) {

            if (k==0 || k==n)

                        return 1;

            return Comb(n-1, k-1) + Comb(n-1,k);

}

Gọi T(n) là thời gian để tính số tổ hợp chập k của n, thì ta có phương trình đệ quy:

T(1) = C1 và T(n) = 2T(n-1) + C2

Giải phương trình này ta được T(n) = O(2n), như vậy là một giải thuật thời gian mũ, trong khi chỉ có một đa thức các bài toán con. Ðiều đó chứng tỏ rằng có những bài toán con được giải nhiều lần.

Chẳng hạn để tính Comb(4,2) ta phải tính Comb(3,1) và Comb(3,2). Ðể tính Comb(3,1) ta phải tính Comb(2,0) và Comb(2,1). Ðể tính Comb(3,2) ta phải tính Comb(2,1) và Comb(2,2). Như vậy để tính Comb(4,2) ta phải tính Comb(2,1) hai lần. Hình sau minh hoạ rõ điều đó.

2. Kỹ thuật quy hoạch động

Áp dụng kỹ thuật quy hoạch động để khắc phục tình trạng trên, ta xây dựng một bảng gồm n+1 dòng (từ 0 đến n) và n+1 cột (từ 0 đến n) và điền giá trị cho O(i,j) theo quy tắc sau: (Quy tắc tam giác Pascal):

O(0,0) = 1;

O(i,0) =1;

O(i,i) = 1 với 0 < i  £ n;

O(i,j) = O(i-1,j-1) + O(i-1,j) với  0 < j < i £ n.

Chẳng hạn với n = 4 ta có bảng bên.

O(n,k) chính là Comb(n,k) và ta có giải thuật như sau:

int Comb(int n, int k) {

int C[n+1,n+1], i, j;

/*1*/    C[0,0] = 1;

/*2*/    for (i = 1; i <= n; i++) {

/*3*/                C[i,0] = 1;

/*4*/                C[i,i] = 1;

 j

i

0

1

2

3

4

0

1

1

1

1

2

1

2

1

3

1

3

3

1

4

1

4

6

4

1

Tam giác Pascal

/*5*/                for (j = 1; j < i; j++) C[i,j]:=C[i-1,j-1]+C[i-1,j];

}

/*6*/    return C[n,k];

}

Vòng lặp /*5*/ thực hiện i-1 lần, mỗi lần O(1). Vòng lặp /*2*/ có i chạy từ 1 đến n, nên nếu gọi T(n) là thời gian thực hiện giải thuật thì ta có:

3. Nhận xét

Thông qua việc xác định độ phức tạp, ta thấy rõ ràng giải thuật quy hoạch động hiệu quả hơn nhiều so với giải thuật đệ qui (n2 < 2n). Tuy nhiên việc sử dụng bảng (mảng hai chiều) như trên còn lãng phí ô nhớ, do đó ta sẽ cải tiến thêm một bước bằng cách sử dụng véctơ (mảng một chiều) để lưu trữ kết quả trung gian. Cách làm cụ thể như sau:

Ta sẽ dùng một véctơ V có n+1 phần tử từ V[0] đến V[n]. Véctơ V sẽ lưu trữ các giá trị tương ứng với dòng i trong tam giác Pascal ở trên. Trong đó V[j] lưu trữ giá trị số tổ hợp chập j của i (Cji) (j = 0 đến i). Dĩ nhiên do chỉ có một véctơ V mà phải lưu trữ nhiều dòng i do đó tại mỗi bước, V chỉ lưu trữ được một dòng và ở bước cuối cùng, V lưu trữ các giá trị ứng với i = n, trong đó V[k] chính là Ckn.

Khởi đầu, ứng với i =1, ta cho V[0] = 1 và V[1] = 1. Tức là C01 = 1 và C11 = 1. Với các giá trị i từ 2 đến n, ta thực hiện như sau:

  • V[0] được gán giá trị 1 tức là C0i = 1. Tuy nhiên giá trị V[0] = 1 đã được gán ở trên, không cần phải gán lại.
  • Với j từ 1 đến i-1, ta vẫn áp dụng công thức Cji = Cj-1i-1 + Cji-1. Nghĩa là để tính các giá trị trong dòng i ta phải dựa vào dòng i-1. Tuy nhiên do chỉ có một véctơ V và lúc này nó sẽ lưu trữ các giá trị của dòng i, tức là dòng i-1 sẽ không còn. Để khắc phục điều này ta dùng thêm hai biến trung gian p1 và p2. Trong đó p1 dùng để lưu trữ Cj-1i-1 và p2 dùng để lưu trữ Cji-1. Khởi đầu p1 được gán V[0] tức là C0i-1 và p2 được gán V[j] tức là Cji-1, V[j] lưu trữ giá trị Cji sẽ được gán bới p1+p2, sau đó p1 được gán bởi p2, nghĩa là khi j tăng lên 1 đơn vị thành j+1 thì p1 là Cji-1 và nó được dùng để tính Cj+1i.
  • Cuối cùng với j = i ta gán V[i] giá trị 1 tức là Cii = 1.