Bài 19: Quy hoạch động nhập môn trong C++ và Python: Fibonacci, đếm đường đi, cái túi 0/1, dãy con tăng dài nhất

Series: Thuật toán cơ bản Độ khó: Trung bình Bài 19 / Thuật toán cơ bản Quy hoạch động

// Thuật toán cơ bản · Bài 19

Quy hoạch động nhập môn: Fibonacci, đếm đường đi, cái túi 0/1, dãy con tăng dài nhất

Thay vì giải đi giải lại cùng một bài toán con, hãy giải mỗi bài toán con đúng một lần và ghi kết quả vào bảng. Ý tưởng chỉ có vậy, nhưng nó giải được những bài mà quay lui phải chạy hàng tỉ năm.

Lời mở đầu

Nếu có một chủ đề “ăn điểm” nhiều nhất trong đề thi học sinh giỏi Tin học thì đó là quy hoạch động (QHĐ, tiếng Anh: dynamic programming). Blog có hơn 120 bài giải bằng QHĐ, từ cấp huyện tới quốc gia. Nghe tên thì đáng sợ, nhưng tư tưởng rất đời thường: bài toán lớn được ghép từ các bài toán con; mỗi bài toán con chỉ giải một lần, ghi kết quả lại, lần sau cần thì tra bảng.

Ở bài 15 em đã thấy quay lui thử mọi khả năng, chậm theo cấp số mũ. Ở bài 18 em thấy tham lam nhanh nhưng hay sai. Quy hoạch động nằm ở giữa: đúng như vét cạn, nhanh gần như tham lam, với điều kiện bài toán có các bài toán con lặp lại.

Bài 15Đệ quy và quay luiBài 16Tìm kiếm nhị phânBài 17Hai con trỏ, cửa sổ trượtBài 18Thuật toán tham lamBài 19Quy hoạch động nhập mônBài 20Thao tác bit, bitmaskBài 21Đồ thị: BFS, DFS, loangBài 22Kỹ năng luyện thiBài 23Tổng ôn và đề thi thử

Trong bài này bạn sẽ học: vì sao đệ quy thuần túy chậm và cách sửa bằng ghi nhớ (đệ quy có nhớ) hoặc lập bảng; năm bước xây dựng một lời giải QHĐ: trạng thái, công thức truy hồi, cơ sở, thứ tự tính, đáp án; ba bài kinh điển: đếm đường đi trên lưới, cái túi 0/1, dãy con tăng dài nhất; bài đổi tiền với mệnh giá bất kỳ mà tham lam làm sai. Có khung chạy tay điền bảng từng ô, mô phỏng bảng cái túi và 8 bài tập kèm gợi ý.

Lộ trình bài viết, bấm vào từng phần để nhảy tới:

Phần 1Từ đệ quy tới ghi nhớPhần 25 bước, lướiPhần 3Cái túi 0/1Phần 4Dãy con tăngPhần 5Đổi tiềnBài tập8 bài + gợi ý

Phần 1Từ đệ quy tới ghi nhớ: dãy Fibonacci

Dãy Fibonacci: $F_0 = 0$, $F_1 = 1$, $F_n = F_{n-1} + F_{n-2}$. Viết thẳng theo công thức bằng đệ quy rất gọn, nhưng tính fib(45) đã mất vài giây, fib(60) thì cả đời không xong. Lý do: cùng một giá trị bị tính lặp đi lặp lại rất nhiều lần.

Cách sửa 1: đệ quy có nhớ (memoization). Dùng mảng nho[n], lần đầu tính fib(n) thì ghi lại; các lần sau trả về ngay. Mỗi giá trị chỉ tính một lần: $O(n)$.
Cách sửa 2: lập bảng (bottom-up). Tính lần lượt f[0], f[1], f[2], … từ nhỏ tới lớn bằng vòng lặp; khi tính f[i] thì f[i-1], f[i-2] đã có sẵn trong bảng. Không cần đệ quy, không lo tràn ngăn xếp. Đây là cách viết QHĐ phổ biến nhất khi thi.

Fibonacci: đệ quy có nhớ và lập bảng

#include <bits/stdc++.h>
using namespace std;

long long nho[95];                     // nho[i] = -1: chưa tính

long long fibNho(int n){               // cách 1: đệ quy có nhớ
    if(n <= 1) return n;
    if(nho[n] != -1) return nho[n];    // đã tính → tra bảng
    return nho[n] = fibNho(n - 1) + fibNho(n - 2);
}

int main(){
    int n;
    cin >> n;                          // n ≤ 90
    memset(nho, -1, sizeof(nho));
    cout << fibNho(n) << "\n";

    vector<long long> f(n + 2);        // cách 2: lập bảng
    f[0] = 0; f[1] = 1;
    for(int i = 2; i <= n; i++) f[i] = f[i - 1] + f[i - 2];
    cout << f[n];
    return 0;
}

from functools import lru_cache
n = int(input())

@lru_cache(maxsize=None)           # cách 1: Python ghi nhớ tự động
def fib_nho(k):
    return k if k <= 1 else fib_nho(k - 1) + fib_nho(k - 2)

print(fib_nho(n))

f = [0, 1] + [0] * n               # cách 2: lập bảng
for i in range(2, n + 1):
    f[i] = f[i - 1] + f[i - 2]
print(f[n])

Hai dấu hiệu của bài quy hoạch động

1. Bài toán con gối nhau: khi chia bài lớn thành bài nhỏ, cùng một bài nhỏ xuất hiện nhiều lần (như $F_3$ ở trên). Nếu các bài con không trùng nhau thì chỉ là chia để trị bình thường.
2. Cấu trúc con tối ưu: lời giải tối ưu của bài lớn được ghép từ lời giải tối ưu của các bài con. Ví dụ: đường đi ngắn nhất từ A tới C qua B thì đoạn A tới B cũng phải ngắn nhất.

Mô phỏng trực quan. Nghe “f(2) bị tính hơn 7 tỉ lần” thì ai cũng thấy ghê, nhưng tận mắt nhìn máy gọi đi gọi lại mới thấm. Em bấm Tiếp để xem f(5) chạy bằng đệ quy thường (đếm từng lời gọi), rồi chạy lại bằng đệ quy có nhớ với mảng nho:

MÔ PHỎNGĐệ quy thường và đệ quy có nhớ: đếm số lời gọiNhập n (1 đến 7). Hàng trên đếm số lần mỗi f(k) bị gọi, hàng ngăn xếp là các lời gọi đang dang dở.

n

ChậmVừaNhanh

lời gọi đang chạybị tính lạilấy từ mảng nhođã ghi nhớchưa có

Phần 2Năm bước xây dựng lời giải và bài đếm đường đi trên lưới

Mọi bài QHĐ, dù dễ hay khó, đều được xây theo đúng năm bước. Em hãy luôn viết ra giấy năm dòng này trước khi code:

Bước	Câu hỏi cần trả lời	Bài đếm đường đi trên lưới
1. Trạng thái	dp[...] nghĩa là gì?	dp[i][j] = số cách đi từ ô $(1, 1)$ tới ô $(i, j)$
2. Truy hồi	Tính dp từ các trạng thái nhỏ hơn thế nào?	Tới $(i, j)$ chỉ có thể từ ô trên hoặc ô trái: dp[i][j] = dp[i-1][j] + dp[i][j-1]; ô có vật cản thì dp = 0
3. Cơ sở	Trạng thái nhỏ nhất bằng bao nhiêu?	dp[1][1] = 1, hàng 0 và cột 0 coi như bằng 0
4. Thứ tự tính	Tính trạng thái nào trước để vế phải luôn có sẵn?	Duyệt hàng $i$ tăng dần, trong mỗi hàng duyệt cột $j$ tăng dần
5. Đáp án	Đáp án là trạng thái nào?	dp[m][n]

Bài toán: lưới $m \times n$, mỗi ô là . (đi được) hoặc # (vật cản). Robot ở ô trái trên, mỗi bước chỉ đi sang phải hoặc xuống dưới. Đếm số đường đi tới ô phải dưới.

Code C++ và Python

#include <bits/stdc++.h>
using namespace std;

long long dp[25][25];

int main(){
    int m, n;
    cin >> m >> n;
    vector<string> g(m + 1);
    for(int i = 1; i <= m; i++){ cin >> g[i]; g[i] = " " + g[i]; }
    for(int i = 1; i <= m; i++){
        for(int j = 1; j <= n; j++){
            if(g[i][j] == '#') dp[i][j] = 0;
            else if(i == 1 && j == 1) dp[i][j] = 1;
            else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    cout << dp[m][n];
    return 0;
}

m, n = map(int, input().split())
g = [' ' * (n + 1)] + [' ' + input().strip() for _ in range(m)]
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
    for j in range(1, n + 1):
        if g[i][j] == '#':
            dp[i][j] = 0
        elif i == 1 and j == 1:
            dp[i][j] = 1
        else:
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
print(dp[m][n])

C++▶ Chạy tay từng dòng codeĐiền bảng dp theo từng hàng: mỗi ô bằng tổng ô phía trên và ô bên trái (hai ô xanh). Ô có vật cản luôn bằng 0.

Dữ liệu vào (stdin) – sửa thoải mái3 4 .... .#.. ....

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4long long dp[25][25];

5

6int main(){

7 int m, n;

8 cin >> m >> n;

9 vector<string> g(m + 1);

10 for(int i = 1; i <= m; i++){ cin >> g[i]; g[i] = " " + g[i]; }

11 for(int i = 1; i <= m; i++){

12 for(int j = 1; j <= n; j++){

13 if(g[i][j] == '#') dp[i][j] = 0;

14 else if(i == 1 && j == 1) dp[i][j] = 1;

15 else dp[i][j] = dp[i - 1][j] + dp[i][j - 1];

16 }

17 }

18 cout << dp[m][n];

19 return 0;

20}

ChậmVừaNhanhRất nhanh

Phần 3Bài toán cái túi 0/1

Có $n$ đồ vật, vật $i$ nặng $w_i$ và có giá trị $v_i$. Túi chở tối đa $W$. Mỗi vật lấy hoặc không lấy (không cắt nhỏ). Chọn các vật để tổng giá trị lớn nhất. Ở bài 18 em đã thấy tham lam thất bại với bài này. Áp dụng năm bước:

• Trạng thái: dp[i][j] = giá trị lớn nhất khi chỉ dùng các vật $1..i$ và túi sức chứa $j$.
• Truy hồi: với vật $i$ có hai lựa chọn. Không lấy: dp[i-1][j]. Lấy (nếu $w_i \le j$): dp[i-1][j - w[i]] + v[i] (dành $w_i$ cho vật $i$, phần còn lại tối ưu với các vật trước). Lấy max hai lựa chọn.
• Cơ sở: dp[0][j] = 0 (không có vật nào). Thứ tự: $i$ tăng dần. Đáp án: dp[n][W].

Độ phức tạp $O(n \cdot W)$: chạy tốt với $n \le 100$, $W \le 10^5$, trong khi vét cạn $2^{100}$ tập con là không tưởng.

Code C++ và Python

#include <bits/stdc++.h>
using namespace std;

int dp[105][1005];

int main(){
    int n, W;
    cin >> n >> W;
    vector<int> w(n + 1), v(n + 1);
    for(int i = 1; i <= n; i++) cin >> w[i] >> v[i];
    for(int i = 1; i <= n; i++){
        for(int j = 0; j <= W; j++){
            dp[i][j] = dp[i - 1][j];
            if(w[i] <= j)
                dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);
        }
    }
    cout << dp[n][W];
    return 0;
}

n, W = map(int, input().split())
w, v = [0], [0]
for _ in range(n):
    a, b = map(int, input().split())
    w.append(a); v.append(b)
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(W + 1):
        dp[i][j] = dp[i - 1][j]
        if w[i] <= j:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i])
print(dp[n][W])

C++▶ Chạy tay từng dòng codeBảng dp[i][j]: hàng i = đã xét i vật đầu, cột j = sức chứa. Mỗi ô so sánh “không lấy vật i” (ô ngay trên) với “lấy vật i” (ô hàng trên, lùi w[i] cột).

Dữ liệu vào (stdin) – sửa thoải mái3 5 2 3 3 4 4 5

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int dp[105][1005];

5

6int main(){

7 int n, W;

8 cin >> n >> W;

9 vector<int> w(n + 1), v(n + 1);

10 for(int i = 1; i <= n; i++) cin >> w[i] >> v[i];

11 for(int i = 1; i <= n; i++){

12 for(int j = 0; j <= W; j++){

13 dp[i][j] = dp[i - 1][j];

14 if(w[i] <= j)

15 dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + v[i]);

16 }

17 }

18 cout << dp[n][W];

19 return 0;

20}

ChậmVừaNhanhRất nhanh

Tiết kiệm bộ nhớ: mảng một chiều

Hàng $i$ chỉ dùng hàng $i - 1$, nên chỉ cần một mảng dp[j], với điều kiện duyệt $j$ giảm dần: for(j = W; j >= w[i]; j--) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);. Duyệt giảm dần để dp[j - w[i]] vẫn là giá trị của hàng cũ (chưa dùng vật $i$). Nếu duyệt tăng dần, một vật có thể bị lấy nhiều lần: đó lại chính là lời giải của bài cái túi không giới hạn (mỗi loại vật lấy bao nhiêu cũng được).

Xem bảng cái túi được điền: sửa danh sách đồ vật rồi bấm Tự chạy. Sau khi điền xong, mô phỏng truy vết ngược từ ô cuối để chỉ ra những vật nào đã được chọn.

MÔ PHỎNGĐiền bảng quy hoạch động cái túi 0/1Mỗi dòng một vật “khối lượng giá trị” (tối đa 6 vật), sức chứa W tối đa 15.

Đang tải mô phỏng…

Phần 4Dãy con tăng dài nhất

Dãy con của một dãy là dãy thu được khi xóa đi một số phần tử, giữ nguyên thứ tự các phần tử còn lại (không cần liên tiếp). Tìm độ dài dãy con tăng ngặt dài nhất (LIS). Ví dụ dãy 5 2 8 6 3 6 9 7 có dãy con tăng dài nhất 2 3 6 9 (hoặc 2 3 6 7), độ dài 4.

• Trạng thái: L[i] = độ dài dãy con tăng dài nhất kết thúc tại phần tử $i$.
• Truy hồi: phần tử $a_i$ nối được vào sau mọi dãy con tăng kết thúc tại $j < i$ có $a_j < a_i$: L[i] = 1 + max(L[j]) với các $j$ như vậy (nếu không có $j$ nào thì L[i] = 1).
• Đáp án: $\max L[i]$ (dãy con dài nhất có thể kết thúc ở bất kỳ đâu). Độ phức tạp $O(n^2)$.

Code C++ và Python

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> a(n), L(n);
    for(int &v : a) cin >> v;
    int best = 0;
    for(int i = 0; i < n; i++){
        L[i] = 1;
        for(int j = 0; j < i; j++)
            if(a[j] < a[i] && L[j] + 1 > L[i])
                L[i] = L[j] + 1;
        best = max(best, L[i]);
    }
    cout << best;
    return 0;
}

n = int(input())
a = list(map(int, input().split()))
L = [1] * n
for i in range(n):
    for j in range(i):
        if a[j] < a[i] and L[j] + 1 > L[i]:
            L[i] = L[j] + 1
print(max(L))

C++▶ Chạy tay từng dòng codeL[i] = độ dài dãy con tăng dài nhất kết thúc tại a[i]. Với mỗi i, quét mọi j < i có a[j] < a[i] để nối dài thêm.

Dữ liệu vào (stdin) – sửa thoải mái8 5 2 8 6 3 6 9 7

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3

4int main(){

5 int n;

6 cin >> n;

7 vector<int> a(n), L(n);

8 for(int &v : a) cin >> v;

9 int best = 0;

10 for(int i = 0; i < n; i++){

11 L[i] = 1;

12 for(int j = 0; j < i; j++)

13 if(a[j] < a[i] && L[j] + 1 > L[i])

14 L[i] = L[j] + 1;

15 best = max(best, L[i]);

16 }

17 cout << best;

18 return 0;

19}

ChậmVừaNhanhRất nhanh

Phần 5Đổi tiền với mệnh giá bất kỳ

Quay lại bài đổi tiền ở bài 18 mà tham lam làm sai với mệnh giá $\{1, 3, 4\}$. Với QHĐ: dp[x] = số tờ ít nhất để trả đúng $x$. Tờ cuối cùng có mệnh giá $c$ nào đó, phần còn lại $x - c$ phải trả tối ưu: dp[x] = min(dp[x - c] + 1) với mọi mệnh giá $c \le x$; cơ sở dp[0] = 0. Độ phức tạp $O(N \cdot m)$. Với $N = 6$: dp = 0, 1, 2, 1, 1, 2, 2, đúng là 2 tờ (3 + 3).

Đổi tiền ít tờ nhất với mệnh giá bất kỳ

#include <bits/stdc++.h>
using namespace std;

int main(){
    int m, N;
    cin >> m >> N;
    vector<int> c(m);
    for(int &x : c) cin >> x;
    const int INF = 1e9;
    vector<int> dp(N + 1, INF);
    dp[0] = 0;
    for(int x = 1; x <= N; x++)
        for(int v : c)
            if(v <= x && dp[x - v] + 1 < dp[x]) dp[x] = dp[x - v] + 1;
    cout << (dp[N] >= INF ? -1 : dp[N]);
    return 0;
}

m, N = map(int, input().split())
c = list(map(int, input().split()))
INF = float('inf')
dp = [0] + [INF] * N
for x in range(1, N + 1):
    for v in c:
        if v <= x and dp[x - v] + 1 < dp[x]:
            dp[x] = dp[x - v] + 1
print(-1 if dp[N] == INF else dp[N])

Ba lỗi hay gặp khi làm QHĐ

1. Định nghĩa trạng thái mơ hồ: không viết rõ dp[i] là gì thì công thức truy hồi sẽ sai. Hãy viết thành câu đầy đủ như ở các phần trên.
2. Sai thứ tự tính: vế phải dùng một ô chưa được tính (còn bằng 0) thì kết quả sai mà không báo lỗi.
3. Quên khởi tạo: bài tìm min phải khởi tạo bằng “vô cùng” (1e9, LLONG_MAX / 2…), bài đếm số cách thường cần lấy dư theo $10^9 + 7$ ngay sau mỗi phép cộng.

Luyện tập trên web

Các bài dưới đây trên blog đều có lời giải chi tiết bằng C++ và Python, xếp từ dễ tới khó. Em hãy tự làm trước rồi mới xem lời giải nhé.

• Frog 2 (AtCoder Educational DP Contest B) (Dễ)
• Cầu Thang Nhà A Phủ (DPSTEPS) (Dễ)
• Công Chúa (DPPRINCESS) (Dễ)
• Gián Ăn (Dễ)
• Dãy Con Tăng Dài Nhất – Bản Dễ (DCTDN1) (Dễ)
• Tổng đoạn con lớn nhất (Kadane) (Dễ)

Xem toàn bộ bài cùng chủ đề: nhãn Quy hoạch động.

Mô phỏng trực quan. Công thức $dp[x] = \min(dp[x-c] + 1)$ đọc thì gọn, nhưng nhiều bạn chưa hình dung “thử từng tờ làm tờ cuối cùng” là thế nào. Em xem bảng dp được điền với mệnh giá 1, 3, 4 và N = 6, rồi truy vết ngược để ra cách đổi 3 + 3, so với tham lam 4 + 1 + 1:

MÔ PHỎNGĐiền bảng đổi tiền ít tờ nhất rồi truy vếtNhập các mệnh giá (tối đa 5) và số tiền N (tối đa 20). Mỗi bước thử một tờ làm tờ cuối cùng.

Mệnh giáN

ChậmVừaNhanh

ô đang điền / tờ đang thửô dp[x − c] được dùngđường truy vếtchưa điền

Bài tậpLuyện quy hoạch động

Bài 1Leo cầu thangDễ

Cầu thang có $n$ bậc ($n \le 10^6$). Mỗi bước em leo 1 hoặc 2 bậc. Có bao nhiêu cách leo lên bậc $n$? In kết quả modulo $10^9 + 7$.

Input

5

Output

8

💡 Gợi ý

Bước cuối cùng lên bậc $n$ xuất phát từ bậc $n - 1$ hoặc $n - 2$: dp[n] = dp[n-1] + dp[n-2], dp[0] = dp[1] = 1. Chính là dãy Fibonacci! Nhớ lấy dư sau mỗi phép cộng.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    const long long MOD = 1000000007;
    long long a = 1, b = 1;            // dp[i-2], dp[i-1]
    for(int i = 2; i <= n; i++){
        long long c = (a + b) % MOD;
        a = b; b = c;
    }
    cout << b;
    return 0;
}

n = int(input())
MOD = 10**9 + 7
a = b = 1
for _ in range(2, n + 1):
    a, b = b, (a + b) % MOD
print(b)

Bài 2Ếch nhảyDễ

Có $n$ hòn đá ($n \le 10^5$), hòn $i$ cao $h_i$. Con ếch ở hòn 1, mỗi lần nhảy sang hòn $i + 1$ hoặc $i + 2$, tốn $|h_i - h_j|$ năng lượng. Tìm năng lượng ít nhất để tới hòn $n$.

Input

4
10 30 40 20

Output

30

💡 Gợi ý

dp[i] = năng lượng ít nhất để tới hòn $i$. Hòn $i$ được nhảy tới từ $i - 1$ hoặc $i - 2$: dp[i] = min(dp[i-1] + |h[i] - h[i-1]|, dp[i-2] + |h[i] - h[i-2]|). Ví dụ: 1 → 2 → 4 tốn $20 + 10 = 30$.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<long long> h(n), dp(n);
    for(auto &v : h) cin >> v;
    dp[0] = 0;
    for(int i = 1; i < n; i++){
        dp[i] = dp[i - 1] + llabs(h[i] - h[i - 1]);
        if(i >= 2) dp[i] = min(dp[i], dp[i - 2] + llabs(h[i] - h[i - 2]));
    }
    cout << dp[n - 1];
    return 0;
}

n = int(input())
h = list(map(int, input().split()))
dp = [0] * n
for i in range(1, n):
    dp[i] = dp[i - 1] + abs(h[i] - h[i - 1])
    if i >= 2:
        dp[i] = min(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]))
print(dp[-1])

Bài 3Nhặt táo trên lướiDễ

Lưới $m \times n$ ($m, n \le 1000$), ô $(i, j)$ có $a_{ij}$ quả táo. Đi từ ô trái trên tới ô phải dưới, mỗi bước sang phải hoặc xuống dưới, nhặt táo ở mọi ô đi qua. Nhặt được nhiều nhất bao nhiêu quả?

Input

3 3
1 3 1
1 5 1
4 2 1

Output

12

💡 Gợi ý

Giống phần 2 nhưng thay “cộng số cách” bằng “lấy max”: dp[i][j] = a[i][j] + max(dp[i-1][j], dp[i][j-1]). Ví dụ: 1 → 3 → 5 → 2 → 1 = 12.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

long long dp[1005][1005];

int main(){
    int m, n;
    cin >> m >> n;
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++){
            long long a; cin >> a;
            if(i == 1) dp[i][j] = dp[i][j - 1] + a;
            else if(j == 1) dp[i][j] = dp[i - 1][j] + a;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + a;
        }
    cout << dp[m][n];
    return 0;
}

m, n = map(int, input().split())
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
    row = list(map(int, input().split()))
    for j in range(1, n + 1):
        if i == 1:
            dp[i][j] = dp[i][j - 1] + row[j - 1]
        elif j == 1:
            dp[i][j] = dp[i - 1][j] + row[j - 1]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + row[j - 1]
print(dp[m][n])

Bài 4Đổi tiền ít tờ nhấtTrung bình

Có $m$ loại mệnh giá ($m \le 100$), mỗi loại không giới hạn số tờ. Trả đúng $N$ ($N \le 10^5$) với ít tờ nhất; không trả được in $-1$.

Input

3 6
1 3 4

Output

2

💡 Gợi ý

Đúng lời giải phần 5: dp[x] = min(dp[x - c] + 1). Đây là phản ví dụ của tham lam ở bài 18: $3 + 3$.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int main(){
    int m, N;
    cin >> m >> N;
    vector<int> c(m);
    for(int &x : c) cin >> x;
    vector<int> dp(N + 1, INT_MAX);
    dp[0] = 0;
    for(int x = 1; x <= N; x++)
        for(int v : c)
            if(v <= x && dp[x - v] != INT_MAX) dp[x] = min(dp[x], dp[x - v] + 1);
    cout << (dp[N] == INT_MAX ? -1 : dp[N]);
    return 0;
}

m, N = map(int, input().split())
c = list(map(int, input().split()))
INF = float('inf')
dp = [0] + [INF] * N
for x in range(1, N + 1):
    for v in c:
        if v <= x and dp[x - v] + 1 < dp[x]:
            dp[x] = dp[x - v] + 1
print(-1 if dp[N] == INF else dp[N])

Bài 5Số cách đổi tiềnTrung bình

Có $m$ loại mệnh giá, mỗi loại không giới hạn. Đếm số cách trả đúng $N$ ($N \le 10^5$), hai cách chỉ khác thứ tự các tờ coi là một. In modulo $10^9 + 7$.

Input

3 5
1 2 5

Output

4

💡 Gợi ý

Để không đếm trùng thứ tự, duyệt mệnh giá ở vòng ngoài, số tiền ở vòng trong: for c: for x = c..N: dp[x] += dp[x - c], dp[0] = 1. Đổi chỗ hai vòng thì sẽ đếm cả các cách khác thứ tự. Bốn cách: 5; 2+2+1; 2+1+1+1; 1+1+1+1+1.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int main(){
    int m, N;
    cin >> m >> N;
    const long long MOD = 1000000007;
    vector<long long> dp(N + 1, 0);
    dp[0] = 1;
    for(int k = 0; k < m; k++){
        int c; cin >> c;
        for(int x = c; x <= N; x++) dp[x] = (dp[x] + dp[x - c]) % MOD;
    }
    cout << dp[N];
    return 0;
}

m, N = map(int, input().split())
MOD = 10**9 + 7
dp = [1] + [0] * N
for c in map(int, input().split()):
    for x in range(c, N + 1):
        dp[x] = (dp[x] + dp[x - c]) % MOD
print(dp[N])

Bài 6Cái túi 0/1Trung bình

$n$ đồ vật ($n \le 100$), vật $i$ nặng $w_i$, giá trị $v_i$; túi chở tối đa $W$ ($W \le 10^5$). Tìm tổng giá trị lớn nhất.

Input

3 8
3 30
4 50
5 60

Output

90

💡 Gợi ý

Phần 3 với mảng một chiều, duyệt $j$ giảm dần để mỗi vật lấy tối đa một lần. Ví dụ: lấy vật 1 và 3 (nặng 8, giá trị 90).

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n, W;
    cin >> n >> W;
    vector<long long> dp(W + 1, 0);
    for(int i = 0; i < n; i++){
        int w; long long v;
        cin >> w >> v;
        for(int j = W; j >= w; j--) dp[j] = max(dp[j], dp[j - w] + v);
    }
    cout << dp[W];
    return 0;
}

n, W = map(int, input().split())
dp = [0] * (W + 1)
for _ in range(n):
    w, v = map(int, input().split())
    for j in range(W, w - 1, -1):
        if dp[j - w] + v > dp[j]:
            dp[j] = dp[j - w] + v
print(dp[W])

Bài 7Dãy con tăng dài nhất (bản lớn)Khá

Cho dãy $n$ số nguyên ($n \le 10^5$). Tìm độ dài dãy con tăng ngặt dài nhất. Cách $O(n^2)$ ở phần 4 sẽ bị TLE.

Input

8
5 2 8 6 3 6 9 7

Output

4

💡 Gợi ý

Giữ mảng t: t[k] = phần tử cuối nhỏ nhất có thể của một dãy con tăng dài $k + 1$. Mảng t luôn tăng, nên với mỗi $a_i$ tìm bằng lower_bound (bài 16) vị trí đầu tiên $\ge a_i$ và ghi đè bằng $a_i$ (hoặc thêm vào cuối nếu $a_i$ lớn hơn tất cả). Độ dài t cuối cùng là đáp án. $O(n \log n)$.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> t;
    for(int i = 0; i < n; i++){
        int x; cin >> x;
        auto it = lower_bound(t.begin(), t.end(), x);
        if(it == t.end()) t.push_back(x);
        else *it = x;
    }
    cout << t.size();
    return 0;
}

from bisect import bisect_left
n = int(input())
t = []
for x in map(int, input().split()):
    p = bisect_left(t, x)
    if p == len(t):
        t.append(x)
    else:
        t[p] = x
print(len(t))

Bài 8Xâu con chung dài nhấtKhá

Cho hai xâu $s$, $t$ (độ dài $\le 3000$). Tìm độ dài xâu con chung dài nhất (LCS): xâu nhận được từ cả $s$ và $t$ bằng cách xóa bớt ký tự (không cần liên tiếp).

Input

ABCBDAB
BDCABA

Output

4

💡 Gợi ý

dp[i][j] = LCS của $i$ ký tự đầu của $s$ và $j$ ký tự đầu của $t$. Nếu $s_i = t_j$: dp[i][j] = dp[i-1][j-1] + 1; ngược lại dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Ví dụ: “BCBA”.

Xem code tham khảo (C++ / Python)

#include <bits/stdc++.h>
using namespace std;

int dp[3005][3005];

int main(){
    string s, t;
    cin >> s >> t;
    int n = s.size(), m = t.size();
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            if(s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
    cout << dp[n][m];
    return 0;
}

s = input().strip()
t = input().strip()
m = len(t)
prev = [0] * (m + 1)
for ch in s:
    cur = [0] * (m + 1)
    for j in range(1, m + 1):
        cur[j] = prev[j - 1] + 1 if ch == t[j - 1] else max(prev[j], cur[j - 1])
    prev = cur
print(prev[m])

Bài tiếp theo · Bài 20

Thao tác bit và duyệt bitmask

AND, OR, XOR, dịch bit, và cách dùng một số nguyên để biểu diễn cả một tập hợp: duyệt mọi tập con chỉ bằng một vòng for.

Học bài 20 →

← Bài 18: Tham lamXem cả series Thuật toán cơ bản

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇

Bản quyền thuộc về Thầy Nguyễn Việt Nam Sơn. Bài viết, lời giải, hình minh hoạ và mã nguồn trên trang là công sức biên soạn của thầy qua nhiều năm giảng dạy. Vui lòng không sao chép, đăng lại hay sử dụng dưới mọi hình thức khi chưa được sự đồng ý của tác giả. Nếu thấy hữu ích, hãy chia sẻ bằng đường link bài gốc nhé. Cảm ơn bạn!