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

Maximum Path Sum in a Triangle

Find the largest sum on a path from the top of a number triangle to its bottom row.

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

  • Replace exponential search with dynamic programming
  • Combine results from the row below
  • Handle negative values and empty input

Đề bài

Xem bản dịch

A number triangle has one value on row 0, two on row 1, and so on. Start at the top and move down one row at a time, each time to the value directly below or the one below and to the right (from position i to i or i + 1). Find the path whose values add up to the most. Trying every path doubles the work each row; working upward from the bottom row keeps it quadratic.

Implement triangle_max_path_sum(triangle).

Input

triangle: The rows from top to bottom; row r has r + 1 values, which may be negative.

Output

Return the largest possible sum of a top-to-bottom path. An empty triangle returns 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

The best path is 4, 7, 9, 8 (position 0, 0, 1, 2), for 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

With negatives, −3, 5, 2 gives 4 while −3, −8, 9 gives −2, so the answer is 4.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Start from the bottom row: the best path from a bottom cell is just its value.

Gợi ý 2

The best path from a cell is its value plus the larger best of the two cells below it.

Gợi ý 3

After processing every row upward, the top cell holds the answer.

Độ phức tạp mong đợi

O(rows²) time, O(rows) extra space

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.