By Long Luo

# 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:

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.

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

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

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