Quy hoạch động 1 chiều: leo thang, đổi xu, chọn không kề

Một chiều không có nghĩa chỉ một công thức

Cùng một mảng dp nhưng mỗi bài có thể lưu một loại đáp án khác. Đếm số cách leo tới bậc i cần cộng số lịch sử hợp lệ. Đổi tổng tiền i bằng ít xu nhất cần lấy min số đồng. Chọn các phần tử không kề nhau để tổng lớn nhất cần lấy max giá trị. Thay phép toán mà không thay định nghĩa và cơ sở sẽ tạo một chương trình có vẻ giống DP nhưng giải sai bài.

Một cách luyện tốt là giữ câu hỏi: “dp[i] trả lời chính xác điều gì?” Sau đó xét quyết định cuối cùng để chia các lời giải thành các trường hợp. Ba bài dưới cùng dựa trên chỉ số một chiều, nhưng mỗi bài dạy một điều kiện cần nhớ khác nhau.

Leo cầu thang: đếm số cách

Mỗi bước dài 1 hoặc 2. Đặt dp[i] là số chuỗi bước đi tới đúng bậc i. Xét bước cuối: nếu dài 1 thì phần trước là cách tới i−1, nếu dài 2 thì phần trước tới i−2. Hai nhóm không trùng nên cộng: dp[i]=dp[i−1]+dp[i−2].

Cơ sở dp[0]=1 và dp[1]=1. Với 0 bậc, có một cách là không đi bước nào. Với n=3, ba cách là 1+1+1, 1+2 và 2+1; thứ tự bước đi làm hai lịch sử sau khác nhau. Nếu đề coi hoán đổi thứ tự là cùng một cách, đây sẽ là một bài đếm khác.

Trong bài nhập môn DP, cả bản nhớ đệ quy, bảng và hai biến đều có code chạy được. Tại đây hãy tập trung vào ý nghĩa phép cộng: ta đang cộng số lời giải, không cộng giá trị tối ưu của hai phương án rồi lấy làm đáp án.

Đổi ít xu: giữ trạng thái không thể đạt

Cho các mệnh giá nguyên dương và được dùng mỗi mệnh giá không giới hạn. Đặt dp[x] là số đồng ít nhất để tạo đúng tổng x. dp[0]=0 vì không cần đồng nào để tạo tổng 0. Các tổng khác ban đầu chưa biết có tạo được không, nên đặt INF.

Nếu đồng cuối có mệnh giá c, phần trước phải tạo đúng x−c. Khi x−c đạt được, ứng viên là dp[x−c]+1; lấy min qua mọi c<=x. Chỉ số giảm vì c dương, nên duyệt tổng x tăng dần là thứ tự hợp lệ.

Với mệnh giá 1,3,4, thuật toán tham lam lấy đồng lớn nhất cho tổng 6 sẽ chọn 4+1+1, ba đồng. DP xét cả phương án dùng đồng cuối 3, kết hợp dp[3]=1 để được hai đồng 3+3. Phản ví dụ này cho thấy không được mặc định bộ mệnh giá nào cũng có tính chất tham lam.

Với mệnh giá 2 và 4, tổng 3 không thể tạo. Kết quả cần là −1 theo quy ước tệp, không phải 0. Số canh INF=target+1 đủ lớn vì mệnh giá nguyên dương khiến một lời giải hợp lệ không cần quá target đồng. Điều này không còn đúng nếu bạn cho phép đồng giá 0 hoặc số âm; code đang yêu cầu đầu vào dương.

Code đổi xu C++ và Python

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int min_coins(const vector<int>& coins,int target){
    int inf=target+1;vector<int> d(target+1,inf);d[0]=0;
    for(int x=1;x<=target;++x)for(int c:coins)
        if(c<=x && d[x-c]!=inf)d[x]=min(d[x],d[x-c]+1);
    return d[target]==inf ? -1:d[target];
}
int main(){
    int n=3,target=6;vector<int> coins={1,3,4};
    if(cin>>n>>target){coins.resize(n);for(int& c:coins)cin>>c;}
    cout<<min_coins(coins,target)<<'\n';
}

import sys

def min_coins(coins,target):
    inf=target+1
    d=[inf]*(target+1);d[0]=0
    for x in range(1,target+1):
        for c in coins:
            if c<=x and d[x-c]!=inf:
                d[x]=min(d[x],d[x-c]+1)
    return -1 if d[target]==inf else d[target]

if __name__=='__main__':
    a=list(map(int,sys.stdin.buffer.read().split()))
    coins=[1,3,4];target=6
    if a:
        n,target=a[:2];coins=a[2:2+n]
    print(min_coins(coins,target))

Không nhập dữ liệu sẽ in 2 cho bộ 1,3,4 và tổng 6. Input riêng là n, target rồi n mệnh giá dương. n và target không âm; danh sách có thể rỗng. target và các phép tính chỉ số phải vừa kiểu int C++, đồng thời số ô target+1 phải phù hợp bộ nhớ. Độ phức tạp O(n·target), bộ nhớ O(target), không phải O(n log target).

Nếu target=0 thì đáp án 0 ngay cả khi không có mệnh giá nào. Nếu không có xu mà target dương thì trả −1. Mệnh giá trùng không đổi đáp án tối thiểu, dù tạo các phép thử lặp; có thể loại trùng nếu cần tối ưu phần hằng số.

Chọn phần tử không kề nhau: lấy hoặc bỏ

Với dãy a, đặt best[i] là tổng lớn nhất chọn được trong i phần tử đầu, không chọn hai vị trí kề nhau và được phép không chọn gì. Xét phần tử cuối của tiền tố, chỉ có hai trường hợp: bỏ nó để giữ best[i−1], hoặc lấy nó rồi chỉ kết hợp với i−2 phần tử trước. Công thức là max(best[i−1], best[i−2]+a[i−1]).

Với a=[2,7,9,3,1], đáp án trên các tiền tố lần lượt là 0,2,7,11,11,12. Kết quả 12 lấy các giá trị 2,9,1. Không nên chọn hai giá trị lớn nhất một cách độc lập: vị trí của chúng và điều kiện không kề mới quyết định có ghép được không.

Code chọn không kề và cơ sở số âm

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
long long best(const vector<long long>& a){
    long long previous=0,two_back=0;
    for(long long x:a){
        long long current=max(previous,two_back+x);
        two_back=previous;previous=current;
    }
    return previous;
}
int main(){
    int n;vector<long long> a={2,7,9,3,1};
    if(cin>>n){a.resize(n);for(auto& x:a)cin>>x;}
    cout<<best(a)<<'\n';
}

import sys

def best(a):
    previous=two_back=0
    for x in a:
        current=max(previous,two_back+x)
        two_back,previous=previous,current
    return previous

if __name__=='__main__':
    a=list(map(int,sys.stdin.buffer.read().split()))
    values=a[1:1+a[0]] if a else [2,7,9,3,1]
    print(best(values))

Tệp này có định dạng riêng: n rồi n giá trị, không nhập sẽ dùng dãy trên và in 12. Có thể chọn tập rỗng, nên dãy toàn số âm trả 0. Nếu đề bắt buộc chọn ít nhất một phần tử, cơ sở và trạng thái phải đổi; không được nộp nguyên quy ước này rồi nhận kết quả 0 cho một dãy toàn âm.

Code giữ hai giá trị tiền tố gần nhất, tính mới bằng max rồi dịch trạng thái. C++ dùng long long, yêu cầu mọi tổng liên quan vừa miền kiểu số. Thời gian O(n), bộ nhớ phụ O(1) cho phần tối ưu; mảng input vẫn có chi phí O(n) trong chương trình minh họa. Bản in các vị trí được chọn cần lưu thêm thông tin hoặc khôi phục bằng một phương pháp khác.

Đừng trộn đổi ít xu với đếm cách đổi xu

Trong bài tối thiểu, thử đồng cuối qua tất cả mệnh giá rồi lấy min là đủ. Trong bài đếm, cùng một tập đồng có thể xuất hiện qua nhiều thứ tự lấy. Duyệt tổng trước rồi xu thường đếm các chuỗi có thứ tự; duyệt loại xu trước rồi tổng tăng có thể đếm tổ hợp theo loại trong mô hình không giới hạn. Phải xác định đề đang đếm thứ gì trước khi chép một vòng lặp quen thuộc.

Tương tự, đổi xu không giới hạn cho phép dùng lại trạng thái có chứa cùng loại xu. Cái túi 0/1 chỉ cho lấy một món một lần, nên khi giảm còn một mảng, chiều duyệt sức chứa phải giữ thông tin của hàng trước. Bài cái túi sẽ chạy tay chính sự khác biệt đó.

Tự kiểm bằng các cách độc lập

Với bài đổi xu, bạn có thể tự kiểm tra trên các tổng nhỏ bằng BFS từ 0 tới target (mỗi bước cộng thêm một mệnh giá xu), thử đủ target = 0, tổng không thể tạo được và phản ví dụ tham lam coins = [1, 3, 4], target = 6.

Với bài chọn phần tử không kề nhau, hãy thử duyệt mọi tập con không chứa hai chỉ số liền kề trên mảng nhỏ (n ≤ 12), gồm cả dãy rỗng, dãy một phần tử và dãy có số âm để phát hiện sớm lỗi ghi đè biến khi tối ưu bộ nhớ xuống O(1).

Luyện ngay trên Big-O Coding

Ba bài lần lượt luyện đếm cách leo, ít xu nhất và tổng không kề lớn nhất. Với mỗi bài, hãy viết một dòng định nghĩa dp và tự tính bảng cho một input nhỏ trước khi dùng bản tối ưu bộ nhớ. Nếu chưa giải thích được cơ sở, hãy giữ bảng đầy đủ để dễ quan sát.

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