# Top-down DP solution

• use an auxiliary 2D array to store the shortest path needed to get to (i, j)

State Definition: dp[i][j]: the shortest path sum to get to point (i, j)
Initialization: dp[0][0] = triangle[0][0]
Transfer Function: dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle[i][j] (if j - 1 and j are both inbound)
Result: minimum value from last row in dp array

``````public int minimumTotal(List<List<Integer>> triangle) {
int[][] dp = new int[triangle.size()][triangle.size()];
dp[0][0] = triangle.get(0).get(0);
for (int i = 1; i < triangle.size(); i++) {
for (int j = 0; j < triangle.get(i).size(); j++) {
int min = Integer.MAX_VALUE;
if (j - 1 >= 0 && j - 1 < triangle.get(i - 1).size()) {
min = Math.min(min, dp[i - 1][j - 1]);
}
if (j >= 0 && j < triangle.get(i - 1).size()) {
min = Math.min(min, dp[i - 1][j]);
}
dp[i][j] = min + triangle.get(i).get(j);
}
}
int result = Integer.MAX_VALUE;
for (int i = 0; i < dp.length; i++) {
if (result > dp[dp.length - 1][i]) {
result = dp[dp.length - 1][i];
}
}
return result;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.