120. Triangle

Problem

Bài toán yêu cầu tìm đường đi nhỏ nhất từ đỉnh xuống đáy của một tam giác số, với mỗi bước chỉ được đi xuống một trong hai số liền kề hàng dưới. Để giải quyết, phương pháp hiệu quả nhất là dùng DP

Approach

Bắt đầu từ hàng dưới cùng của tam giác, mỗi phần tử sẽ lưu tổng nhỏ nhất có thể đạt được từ vị trí đó xuống đáy

Với mỗi phần tử ở hàng trên, ta cập nhật giá trị của nó bằng cách cộng với giá trị nhỏ nhất của hai phần tử liền kề ở hàng dưới

Lặp lại quá trình này cho đến khi lên đến đỉnh tam giác. Giá trị ở đỉnh sẽ là tổng nhỏ nhất cần tìm

Time and space complexity

TC: O(n^2) với n là số hàng của tam giác

SC: O(1)

Solution

typescripttypescript

1function minimumTotal(triangle: number[][]): number {
2    const n = triangle.length;
3    for (let row = n - 2; row >= 0; row--) {
4        for (let col = 0; col <= row; col++)
5            triangle[row][col] += Math.min(triangle[row + 1][col], triangle[row + 1][col + 1])
6    }
7    return triangle[0][0]
8};

💡

Tóm tắt

Dùng bottom-up DP, mỗi bước chọn giá trị nhỏ nhất từ hai số liên kề ở hàng dưới

Có thể cập nhật trực tiếp trên tam giác hoặc dùng mảng phụ để tối ưu không gian

💡

Lý do không bắt đầu từ hàng dưới cùng (n - 1)

Hàng dưới cùng (n - 1) là các điểm kết thúc của mọi đường đi, nên không có hàng nào bên dưới để cộng tiếp

Nếu bạn thử “cập nhật” hàng dưới cùng, bạn sẽ thấy không có gì để so sánh hoặc cập nhật cả vì nó đã là “điểm cuối” rồi

Tại sao lại là hàng n- 2?

Ở hàng n - 2 (hàng áp chót), mỗi phần tử sẽ nhìn xuống hai phần tử liền kề bên dưới (ở hàng n - 1) để quyết định nên đi hướng nào thì tổng là nhỏ nhất

Khi đó, bạn có thể cập nhật giá trị của từng phần tử ở hàng n - 2 bằng cách lấy nó cộng với giá trị nhỏ nhất của hai phần tử bên dưới

Sau khi cập nhật xong hàng n- 2, bạn tiếp tục cập nhật các hàng phía trên, mỗi lần đều dựa vào hàng bên dưới đã được cập nhật

Loading content...

1function minimumTotal(triangle: number[][]): number { 2 const n = triangle.length; 3 for (let row = n - 2; row >= 0; row--) { 4 for (let col = 0; col <= row; col++) 5 triangle[row][col] += Math.min(triangle[row + 1][col], triangle[row + 1][col + 1]) 6 } 7 return triangle[0][0] 8};

Related Posts

Related Posts

120. Triangle

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists

Related Posts

2. Add Two Numbers

3. Longest Substring Without Repeating Characters

3. Longest Substring Without Repeating Characters

4. Median of Two Sorted Arrays

5. Longest Palindromic Substring

6. Zigzag Conversion

9. Palindrome Number

11. Container With Most Water

12. Integer to Roman

13. Roman to Integer

14. Longest Common Prefix

17. Letter Combinations of a Phone Number

19. Remove Nth Node From End of List

20. Valid Parentheses

21. Merge Two Sorted Lists