Quy hoạch động là gì? Từ đệ quy lặp tới trạng thái và bảng

Tại sao cùng một việc lại bị tính nhiều lần?

Bạn cần leo n bậc, mỗi bước đi 1 hoặc 2 bậc. Gọi f(n) là số chuỗi bước đi tới đúng bậc n. Nếu bước cuối dài 1, trước đó phải ở n−1; nếu bước cuối dài 2, trước đó phải ở n−2. Hai nhóm cách đi không giao nhau nên f(n)=f(n−1)+f(n−2).

Đệ quy trực tiếp theo công thức này dễ viết nhưng tạo nhiều lời gọi lặp. Để tính f(5), ta cần f(4) và f(3). Tính f(4) lại cần f(3), trong khi f(3) còn được tính ở nhánh kia. Càng đi sâu, cùng một số bậc còn lại càng xuất hiện nhiều lần.

DP lưu f(3) sau lần tính đầu để nhánh khác lấy lại. Với bài này, các trạng thái phân biệt chỉ là 0 tới n. Ta chuyển từ một cây lời gọi có nhiều nút trùng thành một tập bài toán con mà mỗi phần được xử lý một lần.

Trạng thái phải là một câu có nghĩa

Đừng chỉ viết “dp[i] là đáp án” rồi chuyển ngay sang code. Một câu đủ rõ là: dp[i] bằng số cách đi tới đúng bậc i từ bậc 0, với mỗi bước dài 1 hoặc 2. Câu này chốt đích cần đạt, điểm bắt đầu và hành động được phép.

Nếu đề thêm điều kiện không được bước 2 hai lần liên tiếp, chỉ biết i chưa đủ để quyết định bước tiếp. Cần thêm thông tin bước vừa đi thuộc loại nào, chẳng hạn dp[i][last]. Hai lịch sử cùng tới i nhưng khác last có tương lai hợp lệ khác nhau, nên không được gộp vào một trạng thái duy nhất.

Đó là tiêu chí chọn trạng thái: các lịch sử được gộp phải có cùng khả năng tiếp diễn liên quan tới mục tiêu. Lưu toàn bộ lịch sử thì đủ thông tin nhưng thường quá lớn; bỏ quá nhiều thì tính sai. Kỹ năng DP nằm ở việc giữ đúng phần thông tin cần thiết.

Công thức chuyển và cơ sở

Với bài cơ bản, xét bước cuối cho công thức dp[i]=dp[i−1]+dp[i−2] khi i>=2. Có đúng một cách tới bậc 0 bằng chuỗi bước rỗng, nên dp[0]=1. Với bậc 1, chỉ có bước 1, nên dp[1]=1.

Số cách ở bậc 0 bằng 1 không có nghĩa bạn đã đi một bước. Nó là phần tử trung hòa khi ghép một lựa chọn mới vào lịch sử chưa có gì. Nếu đặt bằng 0 trong cách cộng từ các trạng thái trước, mọi số đếm phía sau có thể bị kéo về 0 hoặc sai lệch.

Khi lập công thức, phải kiểm các nhóm không bỏ sót và không đếm trùng. Với bài đổi tiền, hoán đổi thứ tự lấy đồng xu có thể tính thành cùng một cách hoặc hai cách tùy đề. Một dấu cộng đúng cú pháp chưa bảo đảm công thức đếm đúng đối tượng.

Top-down: hỏi tới đâu tính tới đó

Hàm solve(i) trả kết quả trạng thái i. Nếu đã có trong memo, trả ngay; nếu chưa, tính các trạng thái phụ thuộc rồi lưu kết quả. Code Python dùng functools.cache để ghi nhớ giá trị theo tham số. C++ dùng vector có giá trị −1 làm dấu chưa tính, vì số cách trong miền bài không âm.

Top-down gần với cách suy luận đệ quy nên dễ viết thử. Nó chỉ tính những trạng thái được gọi tới, hữu ích khi không gian trạng thái tổng quát lớn nhưng một truy vấn chỉ chạm tới một phần. Tuy vậy, cache không loại bỏ độ sâu lời gọi: một chuỗi phụ thuộc dài vẫn có thể tràn stack hoặc chạm giới hạn đệ quy.

Nếu kết quả hợp lệ cũng có thể bằng −1, không dùng −1 làm dấu chưa tính trừ khi có mảng seen riêng. Tương tự, giá trị 0 có thể là một đáp án thật, nên điều kiện “memo[i] khác 0 mới là đã tính” thường làm các trạng thái đáp án 0 bị tính lại.

Bottom-up: chọn thứ tự tính hợp lệ

Vì dp[i] phụ thuộc i−1 và i−2, ta đi i tăng dần từ 2 tới n. Mỗi lần đọc trạng thái trước đều đã có kết quả. Đây là thứ tự của quan hệ phụ thuộc, không phải một quy tắc rằng mọi bài DP đều chạy chỉ số tăng.

Với DP trên đoạn, trạng thái dài có thể phụ thuộc đoạn ngắn, nên duyệt theo độ dài. Với cây, kết quả cha có thể cần các con xong trước, nên dùng hậu duyệt. Với bài có chu trình phụ thuộc mà bạn chưa có cách giải hệ phù hợp, chỉ thêm cache vào đệ quy không tự phá được vòng.

Code ba cách trên cùng ví dụ

#include <functional>
#include <iostream>
#include <vector>
using namespace std;
long long top_down(int n){
    vector<long long> memo(n+2,-1);memo[0]=memo[1]=1;
    function<long long(int)> solve=[&](int x){
        if(memo[x]!=-1)return memo[x];
        return memo[x]=solve(x-1)+solve(x-2);
    };
    return solve(n);
}
long long bottom_up(int n){
    vector<long long> d(n+2,0);d[0]=d[1]=1;
    for(int i=2;i<=n;++i)d[i]=d[i-1]+d[i-2];
    return d[n];
}
long long small_memory(int n){
    long long a=1,b=1;
    if(n==0)return a;
    for(int i=2;i<=n;++i){long long c=a+b;a=b;b=c;}
    return b;
}
int main(){
    int n=5;if(cin>>n){}
    if(n<0 || n>90){cerr<<"Can 0 <= n <= 90\n";return 1;}
    cout<<top_down(n)<<' '<<bottom_up(n)<<' '<<small_memory(n)<<'\n';
}

from functools import cache
import sys

def top_down(n):
    @cache
    def solve(x):
        if x<=1:
            return 1
        return solve(x-1)+solve(x-2)
    return solve(n)

def bottom_up(n):
    d=[1]*(n+2)
    for i in range(2,n+1):
        d[i]=d[i-1]+d[i-2]
    return d[n]

def small_memory(n):
    a=b=1
    for _ in range(2,n+1):
        a,b=b,a+b
    return 1 if n==0 else b

if __name__=='__main__':
    a=sys.stdin.buffer.read().split()
    n=int(a[0]) if a else 5
    if not 0<=n<=90:
        raise ValueError('Can 0 <= n <= 90')
    print(top_down(n),bottom_up(n),small_memory(n))

Không nhập dữ liệu sẽ dùng n=5 và in 8 8 8: top-down, bottom-up, rồi bản chỉ giữ hai giá trị gần nhất. Input riêng là một số nguyên n trong [0,90]. Giới hạn này được giữ chung cho hai ngôn ngữ để ví dụ C++ dùng long long có kết quả chính xác và độ sâu đệ quy nhỏ.

Python có số nguyên lớn nhưng code minh họa vẫn kiểm cùng hợp đồng input. Với n lớn hơn, số cách tăng và chi phí phép cộng số nguyên không còn hằng số theo số bit. Nếu đề yêu cầu lấy dư, phải thực hiện phép modulo theo đề ở mỗi bước; đó là một kiểu kết quả khác, không phải cùng số nguyên chính xác đang in ở đây.

Bản small_memory chỉ giữ hai trạng thái cần đọc tiếp. Nó phù hợp khi chỉ hỏi số cách. Nếu muốn liệt kê một lời giải cụ thể hoặc trả lời nhiều câu hỏi về các giá trị trước, bỏ toàn bộ bảng có thể không còn đáp ứng yêu cầu. Tối ưu bộ nhớ nên làm sau khi trạng thái, công thức và mục tiêu đã rõ.

Độ phức tạp không chỉ nhìn số vòng for

Có n+1 trạng thái, mỗi trạng thái cộng hai giá trị, nên trong mô hình phép toán số nguyên vừa kiểu máy, top-down và bottom-up cần O(n) thời gian. Bản memo và bảng dùng O(n) bộ nhớ; top-down còn có stack O(n). Bản hai biến giảm bộ nhớ phụ về O(1).

Một bài có dp[n][m] chưa chắc là O(nm): nếu mỗi ô thử thêm k lựa chọn, tổng có thể O(nmk). Nếu việc chuyển cần sao chép một xâu dài hoặc tra một cấu trúc logarit, phải tính cả chi phí đó. Câu “số trạng thái nhân công mỗi trạng thái” buộc bạn nhìn đủ hai phần.

Không phải mọi đệ quy có nhớ đều là lời giải nhanh. Nếu trạng thái là mọi tập con của n phần tử, số trạng thái có thể tới 2 mũ n. Memo tránh tính trùng nhưng không làm một không gian trạng thái quá lớn tự biến thành tuyến tính.

Nhận biết bài DP từ yêu cầu

Các bài đếm số cách, tối đa giá trị hoặc tối thiểu chi phí thường có khả năng dùng DP, nhưng từ khóa thôi chưa đủ. Hãy hỏi: sau khi quyết định phần cuối hoặc phần đầu, phần còn lại có cùng dạng bài toán không? Nhiều cách quyết định có dẫn tới cùng trạng thái con không? Có thể gộp lịch sử mà vẫn giữ thông tin cần cho tương lai không?

Bài trộm nhà không kề nhau dùng lựa chọn lấy hoặc bỏ nhà cuối, cần biết đáp án tới những vị trí trước. Bài đổi ít xu cần thử đồng cuối cùng và tối ưu số xu cho tổng nhỏ hơn. Cái túi thêm giới hạn tài nguyên, nên trạng thái thường giữ số món đã xét và sức chứa. Những bài này dùng chung phương pháp suy nghĩ nhưng có công thức khác nhau.

Kiểm thử và quy trình tự làm

Bạn cũng có thể tự kiểm tra kết quả đếm số cách leo cầu thang bằng công thức tổ hợp: nếu dùng k bước bậc 2 thì còn n − 2k bước bậc 1, tổng cộng có n − k bước và C(n − k, k) cách xếp vị trí cho các bước bậc 2. Cộng tổng C(n − k, k) với mọi k ≥ 0 thỏa 2k ≤ n sẽ cho kết quả khớp với cả ba cách cài đặt quy hoạch động.

Khi gặp bài mới, viết câu định nghĩa trạng thái, lập một ví dụ nhỏ có thể liệt kê bằng tay, ghi công thức và cơ sở, rồi vẽ quan hệ phụ thuộc để chọn thứ tự. Sau đó mới viết code và so với vét cạn trên input nhỏ. Cuối cùng mới cân nhắc giảm chiều hoặc đổi cấu trúc để tối ưu.

Luyện ngay trên Big-O Coding

Leo cầu thang luyện đếm cách và cơ sở dp[0]. Trộm nhà luyện tối đa với quyết định lấy/bỏ. Đổi ít xu luyện tối thiểu và trạng thái không thể đạt. Hãy viết bằng lời ý nghĩa dp trước khi cài từng bài để tránh mang một công thức sang ba mục tiêu khác nhau.

Câu hỏi thường gặp

Nguồn tham khảo

• CP-Algorithms: Introduction to DP
• Python: functools.cache
• MIT 6.006: Introduction to Algorithms