Bài gợi ý: Đường đi có tổng lớn nhất
Tóm tắt: Bạn xuất phát từ ô \((1, 1)\) trên bảng kích thước \(n \times m\), chỉ được đi sang phải hoặc đi xuống dưới để tới ô \((n, m)\). Hãy tìm một đường đi sao cho tổng các số trên các ô đi qua đạt giá trị lớn nhất.

Xét bảng \(4 \times 4\) trong đề bài. Nếu đi theo lộ trình \((1,1) \to (1,2) \to (2,2) \to (3,2) \to (3,3) \to (3,4) \to (4,4)\), ta lần lượt đi qua các ô chứa số \(4, 3, 2, 5, 6, 7, 2\) [0]. Tổng điểm thu được là \(4 + 3 + 2 + 5 + 6 + 7 + 2 = 29\) [0].

Bảng có kích thước lên tới \(1000 \times 1000\) [0]. Nếu thử duyệt từng nhánh đường đi, số lượng cách đi sẽ cực kỳ lớn và chương trình chạy không kịp. Nhưng để bước vào ô \((i, j)\), ta chỉ có đúng hai cách: đi từ ô phía trên \((i - 1, j)\) xuống, hoặc đi từ ô bên trái \((i, j - 1)\) sang.

Vì vậy, ta không cần tìm lại toàn bộ hành trình từ đầu. Ta chỉ cần lưu lại tổng điểm lớn nhất để đến được từng ô. Kỹ thuật nhớ kết quả của các bước trước để tính bước sau gọi là quy hoạch động (DP). Gọi \(dp[i][j]\) là tổng lớn nhất khi đi từ \((1, 1)\) tới \((i, j)\), công thức tính là \(dp[i][j] = a[i][j] + \max(dp[i - 1][j], dp[i][j - 1])\).

Do mỗi ô \(a_{i, j} \le 10^{10}\), tổng đường đi sẽ vượt quá giới hạn của số nguyên thông thường, nên bạn hãy dùng kiểu long long [0]. Bạn chỉ cần khởi tạo \(dp[1][1] = a[1][1]\), chạy hai vòng lặp for (int i = 1; i <= n; ++i) và for (int j = 1; j <= m; ++j) để điền bảng, rồi in ra kết quả tại dp[n][m].