DP trên lưới: đếm đường đi và tối ưu tổng giá trị

Bảng ô vuông là một đồ thị có thứ tự

Mỗi ô là một đỉnh, mỗi bước hợp lệ là một cạnh. Nếu chỉ được sang phải hoặc xuống dưới, một bước luôn tăng hàng hoặc cột, không thể quay lại ô cũ. Nhờ không có chu trình phụ thuộc, ta tính từ góc trên trái tới dưới phải theo từng hàng.

Hai bài quen thuộc là đếm số đường và tìm đường có tổng giá trị lớn nhất. Chúng dùng cùng hướng phụ thuộc nhưng trạng thái khác ý nghĩa. Một ô có nhiều đường đi tới không nhất thiết có tổng giá trị tối ưu lớn hơn, nên không thể dùng chung một con số cho cả hai câu hỏi.

Input minh họa gồm các hàng [1,2,3], [4,X,2], [1,5,1], với X là ô cản. Bắt đầu ở (0,0), kết thúc ở (2,2), và tổng đường đi tính cả giá trị ô đầu lẫn ô cuối. Chốt quy ước này trước khi viết cơ sở để tránh cộng thiếu hoặc cộng hai lần.

Đếm đường: cộng hai nhóm không giao nhau

Đặt ways[i][j] là số đường hợp lệ từ ô đầu tới ô (i,j). Bước cuối chỉ có thể từ trên xuống hoặc từ trái sang, nên hai nhóm đường được phân biệt theo hướng bước cuối. Cộng ways[i−1][j] và ways[i][j−1] nếu các ô đó tồn tại.

Ô bắt đầu có một đường rỗng dẫn tới chính nó, nên ways[0][0]=1 nếu không bị chặn. Ô cản có ways=0 và được bỏ qua. Duyệt từ hàng đầu tới cuối, trong mỗi hàng từ trái sang phải để các giá trị cần đọc đã xong.

Không có cản thì số đường còn liên quan tới tổ hợp số bước xuống và sang phải. Khi có cản tùy vị trí, công thức tổ hợp đơn giản không trực tiếp trừ được các đường sai nếu chưa phân tích giao nhau; DP theo từng ô giữ quy tắc rõ ràng hơn.

Tối đa tổng: chỉ cộng từ một đường thật

Đặt best[i][j] là tổng lớn nhất của một đường hợp lệ tới ô đó. Nếu tới được từ trên hoặc trái, lấy giá trị tốt hơn của các ô trước rồi cộng giá trị ô hiện tại. Ô đầu có best bằng đúng giá trị của nó. Ô cản và ô không có tiền nhiệm tới được mang dấu không thể đạt.

Với lưới ví dụ, hàng đầu có tổng 1,3,6. Hàng 1 có 5, không thể đạt ở ô cản, rồi 8 từ trên xuống. Hàng cuối lần lượt 6,11,12. Ô đích chọn đường từ trái có 11 rồi cộng 1, tốt hơn đường từ trên có 8 rồi cộng 1.

Nếu mọi giá trị đều âm, đáp án hợp lệ vẫn có thể âm. Khởi tạo mọi best bằng 0 sẽ tạo cảm giác có thể bắt đầu giữa đường để tránh số âm. Chẳng hạn lưới một hàng [−5,−2] chỉ có tổng −7, không phải 0 hay −2. Cần phân biệt “chưa tới được” với một giá trị thấp nhưng có đường thật.

Code C++ và Python

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const long long NEG=-(1LL<<60),MOD=1000000007;
pair<long long,long long> solve(const vector<vector<string>>& a){
    int n=a.size(),m=a[0].size();
    vector<vector<long long>> ways(n,vector<long long>(m)),best(n,vector<long long>(m,NEG));
    for(int i=0;i<n;++i)for(int j=0;j<m;++j){
        if(a[i][j]=="X")continue;
        long long value=stoll(a[i][j]);
        if(i==0 && j==0){ways[i][j]=1;best[i][j]=value;continue;}
        if(i>0){
            ways[i][j]=(ways[i][j]+ways[i-1][j])%MOD;
            if(best[i-1][j]!=NEG)best[i][j]=max(best[i][j],best[i-1][j]+value);
        }
        if(j>0){
            ways[i][j]=(ways[i][j]+ways[i][j-1])%MOD;
            if(best[i][j-1]!=NEG)best[i][j]=max(best[i][j],best[i][j-1]+value);
        }
    }
    return {ways[n-1][m-1],best[n-1][m-1]};
}
int main(){
    int n=3,m=3;vector<vector<string>> a={{"1","2","3"},{"4","X","2"},{"1","5","1"}};
    if(cin>>n>>m){a.assign(n,vector<string>(m));for(auto& row:a)for(auto& x:row)cin>>x;}
    auto [count,best]=solve(a);cout<<count<<' ';
    if(best==NEG)cout<<"NO_PATH\n";else cout<<best<<'\n';
}

import sys
MOD=1000000007

def solve(a):
    n,m=len(a),len(a[0])
    ways=[[0]*m for _ in range(n)]
    best=[[None]*m for _ in range(n)]
    for i in range(n):
        for j in range(m):
            if a[i][j]=='X':
                continue
            value=int(a[i][j])
            if i==j==0:
                ways[i][j]=1;best[i][j]=value
                continue
            for u,v in ((i-1,j),(i,j-1)):
                if u>=0 and v>=0:
                    ways[i][j]=(ways[i][j]+ways[u][v])%MOD
                    if best[u][v] is not None:
                        candidate=best[u][v]+value
                        if best[i][j] is None or candidate>best[i][j]:
                            best[i][j]=candidate
    return ways[-1][-1],best[-1][-1]

if __name__=='__main__':
    t=sys.stdin.read().split()
    a=[['1','2','3'],['4','X','2'],['1','5','1']]
    if t:
        n,m=map(int,t[:2]);a=[t[2+i*m:2+(i+1)*m] for i in range(n)]
    count,best=solve(a);print(count,'NO_PATH' if best is None else best)

Không nhập thì chương trình in 2 12: số đường và tổng lớn nhất. Input riêng có n,m dương rồi n hàng, mỗi hàng m token. Token X là cản; các token khác là số nguyên có thể âm. Chỉ được đi xuống hoặc sang phải. Không có đường thì in số cách 0 và NO_PATH.

Code C++ dùng NEG bằng −2 mũ 60 để đánh dấu không thể tới, còn Python dùng None. Cần bảo đảm mọi giá trị và tổng hữu hạn của ví dụ C++ nằm lớn hơn NEG và các phép cộng vừa long long. Một miền đủ an toàn để học là n,m không quá 1.000 và trị tuyệt đối mỗi ô không quá một tỷ; đó là giới hạn số học minh họa, không phải lời hứa mọi input cỡ đó đều qua thời gian hoặc bộ nhớ của mọi đề.

Số đường được lấy dư 1.000.000.007. Kết quả tối ưu tổng không lấy dư vì modulo không giữ thứ tự lớn bé. Nếu đề yêu cầu số đường chính xác, dùng kiểu số hoặc cách lưu thích hợp thay cho cùng phép lấy dư.

Đừng suy khả năng đi tới từ số cách modulo

Một số đường dương có thể chia hết cho modulo và cho phần dư 0. Vì vậy điều kiện ways[i][j]==0 không tự chứng minh ô đó không tới được. Code giữ trạng thái best riêng; nó chỉ nhận ứng viên nếu tiền nhiệm có giá trị hữu hạn thật.

Đây là khác biệt giữa “không có cấu hình” và “số cấu hình có phần dư bằng 0”. Với input nhỏ hai khái niệm thường trùng trong quan sát, nhưng với lưới lớn số cách có thể rất lớn. Giữ ý nghĩa trạng thái tách bạch giúp tránh lỗi chỉ lộ trên dữ liệu lớn.

Nếu chỉ làm bài đếm modulo, ways bằng 0 vẫn là giá trị đầu ra đúng và không cần phân loại khả năng đi tới riêng. Vấn đề xuất hiện khi bạn dùng con số đó làm cờ để điều khiển một mục tiêu khác như tối ưu tổng hoặc truy vết.

Ô biên và trường hợp một ô

Hàng đầu không có ô phía trên; cột đầu không có ô bên trái. Code kiểm chỉ số trước khi đọc thay vì truy cập hàng −1 hoặc cột −1. Trong Python, chỉ số âm còn có thể âm thầm trỏ tới cuối list, làm lỗi khó nhận ra hơn một thông báo vượt biên.

Lưới 1×1 không bị chặn có đúng một đường và tổng bằng giá trị ô đó. Nếu ô đầu hoặc ô cuối là X, không có đường. Trong một hàng duy nhất, gặp một ô cản làm mọi ô phía sau không tới được; không được khởi tạo cả hàng đầu bằng 1 mà quên xử lý cản.

Giảm còn một hàng và khôi phục đường

Bảng đầy đủ cần O(nm) thời gian, O(nm) bộ nhớ. Vì một ô chỉ đọc phía trên và bên trái, có thể giảm trạng thái còn một hàng O(m). Khi cập nhật d[j], giá trị cũ ở d[j] là ô trên, còn d[j−1] đã mới là ô trái. Tới ô cản phải đặt lại trạng thái ở cột đó, không giữ giá trị từ hàng trước.

Nếu cần in một đường tối ưu, có thể lưu hướng tiền nhiệm cho từng ô khi cải thiện, hoặc dùng phương pháp tái dựng phù hợp. Bản một hàng không tự lưu mọi lựa chọn trong quá khứ. Với các tổng bằng nhau, chọn một hướng theo quy tắc ổn định nếu đề chỉ cần một đường; nếu đề có yêu cầu phụ thì cần xử lý yêu cầu đó riêng.

Khi luật đi thay đổi thì công thức có còn đúng?

Cho thêm bước chéo xuống-phải thì bổ sung một tiền nhiệm nếu các đường vẫn được phân nhóm theo bước cuối và không tạo vòng. Cho đi lên hoặc trái có thể tạo chu trình, lúc đó vòng duyệt hàng/cột hiện tại không còn là thứ tự phụ thuộc hợp lệ. Cần xem bài thành đường đi trên đồ thị và chọn phương pháp theo trọng số, mục tiêu cùng ràng buộc.

Bài “đi qua mọi ô đúng một lần” còn có trạng thái đã thăm các ô và hoàn toàn khác đếm đường đơn điệu. Bài tìm tổng nhỏ nhất thay max bằng min cùng dấu không thể đạt phù hợp; không được chỉ đổi tên hàm nhưng vẫn khởi tạo cho bài tối đa.

Kiểm bằng liệt kê mọi đường trên lưới nhỏ

Để tự kiểm tra trên lưới nhỏ (3×3 hoặc 4×4), bạn có thể dùng đệ quy quay lui liệt kê mọi đường đi chỉ sang phải/xuống dưới không chạm ô cản X, trực tiếp đếm số đường và tìm tổng lớn nhất để đối chiếu trên các ca ô xuất phát bị chặn, lưới 1×1 mang số âm, đường đi có tổng bằng 0 và lưới hoàn toàn bị khóa đường tới đích.

Tự làm thêm lưới 2×2 không cản để có hai đường, rồi chặn một ô không phải đầu/cuối để chỉ còn một. Đặt giá trị âm vào ô đầu để kiểm chương trình luôn tính nó. Những ca nhỏ này thường chỉ ra lỗi cơ sở nhanh hơn một lưới lớn ngẫu nhiên khó chạy tay.

Luyện ngay trên Big-O Coding

Bài đếm đường và bài có ô cản luyện cách cộng trạng thái. Bài tổng chi phí nhỏ nhất dùng cùng mô hình phải/xuống nhưng đổi mục tiêu sang min; hãy thiết kế dấu không thể đạt và cơ sở trước khi chuyển từ code tối đa của ví dụ. Đọc rõ tổng có tính ô đầu hay không theo đề từng bài.

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

Nguồn tham khảo

• CSES: Grid Paths I
• CP-Algorithms: Introduction to DP
• Python FAQ: multidimensional lists