Số điểm ban đầu tối thiểu để đến đích

Cho lưới các ô có giá trị điểm (dương hoặc âm). Bắt đầu từ góc trên trái, chỉ được đi xuống hoặc sang phải, đến góc dưới phải. Tại mỗi ô, điểm thay đổi theo giá trị ô đó. Tìm số điểm ban đầu tối thiểu (>0) để có thể hoàn thành hành trình mà không bao giờ bị điểm ≤ 0.

Đầu vào và Đầu ra

Đầu vào: Ma trận 3x3:
-2  -3  3
-5 -10  1
10  30 -5

Đầu ra: Minimum Points Required = 7

Thuật toán (Quy hoạch động ngược)

Tính ngược từ đích về đầu. minToken[i][j] = điểm tối thiểu cần có khi **vừa bước vào** ô (i,j) để có thể đến đích an toàn.

1. Ô đích (m-1,n-1): nếu giá trị > 0 thì cần 1 điểm, ngược lại cần 1 + |giá trị|.
2. Điền cột cuối và hàng cuối (chỉ có 1 hướng đi).
3. Các ô còn lại: rem = min(minToken[i+1][j], minToken[i][j+1]), minToken[i][j] = max(1, rem - matrix[i][j]).
4. Kết quả: minToken[0][0].

Ví dụ C++

#include <iostream>
#include <cmath>
#define ROW 3
#define COL 3
using namespace std;

int tokens[ROW][COL] = {{-2,-3,3}, {-5,-10,1}, {10,30,-5}};

int max(int a, int b) { return (a>b)?a:b; }

int minInitPoints() {
    int minToken[ROW][COL];
    int m=ROW, n=COL;
    minToken[m-1][n-1] = tokens[m-1][n-1] > 0 ? 1 : abs(tokens[m-1][n-1]) + 1;

    for(int i=m-2;i>=0;i--) minToken[i][n-1] = max(minToken[i+1][n-1] - tokens[i][n-1], 1);
    for(int j=n-2;j>=0;j--) minToken[m-1][j] = max(minToken[m-1][j+1] - tokens[m-1][j], 1);

    for(int i=m-2;i>=0;i--)
        for(int j=n-2;j>=0;j--) {
            int remPoint = min(minToken[i+1][j], minToken[i][j+1]);
            minToken[i][j] = max(remPoint - tokens[i][j], 1);
        }
    return minToken[0][0];
}

int main() {
    cout << "Minimum Points Required: " << minInitPoints();
}

Kết quả

Minimum Points Required: 7