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

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$.

2. State Analysis:

$dp[0][0]=c[0][0]$

3. 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:

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.

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]$$

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]$

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. 😉😃💗