Tất cả thử thách
Trung bình 0 đã giải Tỷ lệ chấp nhận 0%

Đường đi có tổng lớn nhất trong tam giác số

Tìm tổng lớn nhất trên một đường đi từ đỉnh tam giác số xuống hàng cuối.

Bạn sẽ học được gì

  • Thay tìm kiếm hàm mũ bằng quy hoạch động
  • Kết hợp kết quả từ hàng bên dưới
  • Xử lý giá trị âm và đầu vào rỗng

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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.

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.