Đề bài
Một tam giác số có một giá trị ở hàng 0, hai giá trị ở hàng 1, và cứ thế tiếp tục. Bắt đầu từ đỉnh, mỗi bước bạn đi xuống một hàng, tới ô ngay bên dưới hoặc ô bên dưới lệch sang phải (từ vị trí i sang i hoặc i + 1). Hãy tìm đường đi có tổng các giá trị lớn nhất. Thử mọi đường đi thì khối lượng công việc tăng gấp đôi sau mỗi hàng; còn tính ngược từ hàng cuối lên thì chỉ mất thời gian bậc hai.
Hãy viết triangle_max_path_sum(triangle).
Đầu vào
triangle: Các hàng từ trên xuống dưới; hàng r có r + 1 giá trị, có thể âm.
Đầu ra
Trả về tổng lớn nhất có thể của một đường đi từ đỉnh xuống đáy. Tam giác rỗng thì trả về 0.
Ràng buộc
0 ≤ rows ≤ 100; −1000 ≤ value ≤ 1000
Ví dụ
Đầu vào:
triangle = [
[4],
[7, 2],
[1, 9, 5],
[6, 3, 8, 2]
]
Kết quả mong đợi:
expected = 28
Đầu vào:
std::vector<std::vector<long long>> triangle = {
{4},
{7, 2},
{1, 9, 5},
{6, 3, 8, 2}
};
Kết quả mong đợi:
long long expected = 28;
Đầu vào:
long[][] triangle = new long[][] {
new long[] {4},
new long[] {7, 2},
new long[] {1, 9, 5},
new long[] {6, 3, 8, 2}
};
Kết quả mong đợi:
long expected = 28;
Giải thích
Đường đi tốt nhất là 4, 7, 9, 8 (vị trí 0, 0, 1, 2), tổng là 28.
Đầu vào:
triangle = [
[-3],
[5, -8],
[-1, 2, 9]
]
Kết quả mong đợi:
expected = 4
Đầu vào:
std::vector<std::vector<long long>> triangle = {
{-3},
{5, -8},
{-1, 2, 9}
};
Kết quả mong đợi:
long long expected = 4;
Đầu vào:
long[][] triangle = new long[][] {
new long[] {-3},
new long[] {5, -8},
new long[] {-1, 2, 9}
};
Kết quả mong đợi:
long expected = 4;
Giải thích
Khi có số âm, −3, 5, 2 cho tổng 4 còn −3, −8, 9 cho −2, nên đáp án là 4.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Bắt đầu từ hàng cuối: đường đi tốt nhất từ một ô ở đáy chính là giá trị của ô đó.
Gợi ý 2
Đường đi tốt nhất từ một ô bằng giá trị của ô cộng với giá trị tốt hơn trong hai ô bên dưới.
Gợi ý 3
Sau khi xử lý ngược lên hết mọi hàng, ô ở đỉnh chứa đáp án.
Độ phức tạp mong đợi
thời gian O(rows²), bộ nhớ phụ O(rows)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.