# Dynamic programming - Bottom up approach - Java with explanation

• public class NumArray {

``````private int sum[][];

public NumArray(int[] nums) {
int n = nums.length;
sum = new int[n][n];

//init the base case
for (int i = 0; i < n; i++) {
sum[i][i] = nums[i];
}

// using dp, go diagonally and process all sums, O(n^2) time with O(n^2) space.
for (int i = 0, d = 0; i < n; i++, d = 0) {
for (int j = i + 1; j < n; j++, d++) {
// current location equals the previous sum on the top left plus the nums[d].
sum[d][j] = sum[d + 1][j] + sum[d][d];
}
}
}

public int sumRange(int i, int j) {
return sum[i][j]; //O(1)
}
``````

}

I'm just posting this here in case anyone wanted to see a bottom up dynamic programming approach.

Since the problem mentioned dynamic programming, I started off with a bottom up approach instead of using memoization.

It has a O(n^2) init runtime/space. O(1) query.

I saw other better solutions with O(n) init runtime/space and O(1) query.

This solution generates this 2d array:

``````-2 -2  1 -4 -2 -3
0  0  3 -2  0 -1
0  0  3 -2  0 -1
0  0  0 -5 -3 -4
0  0  0  0  2  1
0  0  0  0  0 -1

-2,  0,  3, -5,  2, -1
-2,  3, -2, -3, 1
1,  1,  0, -4
-4,  0, -1
-2, -1
-3``````

• Hello Ronny, thanks for the explanation.

I'm writing code in Ruby, and in case someone would read the post that this DP approach is out of time if you are using in Ruby. I think the O(n) preprocessing one is the perfect soluiton.

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