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.

I initially thought about this because I related it to subset-sum which is an NP-Complete problem.

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
```