[LeetCode][120. Triangle] Dynamic Programming: Top-Down and Bottom-Up Approach

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 3.5k 阅读时长 ≈ 3 分钟

By Long Luo

This article is the solution Dynamic Programming Space O(n) Solutions: Top-Down and Bottom-Up Approaches of Problem 120. Triangle.

Intuition

This problem is a classic and typical dynamic programming problem. We can break the large problem into sub-problems.

We can use both the Top-Down and Bottom-Up approach to solve this problem.

Top-Down Approach

  1. State definition:

\(dp[i][j]\) represents the minimum path sum of row \(i\) and column \(j\).

  1. State Analysis:

\(dp[0][0]=c[0][0]\)

  1. The State Transfer Equation:

\[ dp[i][j] = \begin{cases} dp[i-1][0] + c[i][0] & j=0 \\ dp[i-1][i-1] + c[i][i] & j==i \\ min(dp[i-1][j-1],dp[i-1][j]) + c[i][j] & 0 < j < i \\ \end{cases} \]

so we can easily write such code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int minimumTotal(List<List<Integer>> triangle) {
    if (triangle == null || triangle.size() == 0) {
        return 0;
    }

    int len = triangle.size();
    int[][] dp = new int[len][len];
    dp[0][0] = triangle.get(0).get(0);
    for (int i = 1; i < len; i++) {
        dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
        dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);
        for (int j = 1; j < i; j++) {
            dp[i][j] = Math.min(dp[i - 1][j - 1] + triangle.get(i).get(j), dp[i - 1][j] + triangle.get(i).get(j));
        }
    }

    int min = dp[len - 1][0];
    for (int i = 1; i < len; i++) {
        min = Math.min(min, dp[len - 1][i]);
    }

    return min;
}

In fact, \(dp[i][j]\) is only relevant to \(dp[i-1][j]\), but \(dp[i-2][j]\) and previous states are irrelevant, so we don’t have to store these states. We can only use extra \(O(2n)\) space: two one-dimensional arrays of length \(n\) for the transfer, and map \(i\) to one of the one-dimensional arrays according to the parity, then \(i-1\) is mapped to the other one-dimensional array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int minimumTotal(List<List<Integer>> triangle) {
    int len = triangle.size();
    int[][] dp = new int[2][len];

    dp[0][0] = triangle.get(0).get(0);
    for (int i = 1; i < len; i++) {
        int cur = i % 2;
        int prev = 1 - cur;

        dp[cur][0] = dp[prev][0] + triangle.get(i).get(0);
        dp[cur][i] = dp[prev][i - 1] + triangle.get(i).get(i);
        for (int j = 1; j < i; j++) {
            dp[cur][j] = Math.min(dp[prev][j - 1], dp[prev][j]) + triangle.get(i).get(j);
        }
    }

    int min = dp[(len - 1) % 2][0];
    for (int i = 1; i < len; i++) {
        min = Math.min(min, dp[(len + 1) % 2][i]);
    }

    return min;
}

We enumerate \(j\) decreasingly from \(i\) to \(0\), so that we only need a one-dimensional array \(dp\) of length \(n\) to complete the state transition.

\[ dp[j] = min(dp[j-1], dp[j]) + c[i][j] \]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int minimumTotal(List<List<Integer>> triangle) {
    int len = triangle.size();

    int[] dp = new int[len];
    dp[0] = triangle.get(0).get(0);

    for (int i = 1; i < len; i++) {
        dp[i] += dp[i - 1] + triangle.get(i).get(i);

        for (int j = i - 1; j > 0; j--) {
            dp[j] = Math.min(dp[j - 1], dp[j]) + triangle.get(i).get(j);
        }

        dp[0] += triangle.get(i).get(0);
    }

    int min = dp[0];
    for (int i = 1; i < len; i++) {
        min = Math.min(min, dp[i]);
    }

    return min;
}

Analysis

  • Time Complexity: \(O(n^2)\).
  • Space Complexity: \(O(n)\).

Bottom-Up Approach

The state transfer equation of bottom-up approach is:

\(dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + c[i][j]\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int minimumTotal(List<List<Integer>> triangle) {
    int len = triangle.size();

    int[] dp = new int[len];

    for (int i = 0; i < len; i++) {
        dp[i] = triangle.get(len - 1).get(i);
    }

    for (int i = len - 2; i >= 0; i--) {
        for (int j = 0; j <= i; j++) {
            dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
        }
    }

    return dp[0];
}

Analysis

  • Time Complexity: \(O(n^2)\).
  • Space Complexity: \(O(n)\).

All suggestions are welcome. If you have any query or suggestion please comment below. Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗