Dynamic programming - Bottom up approach - Java with explanation


  • 1
    R

    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

  • 0
    I

    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.


Log in to reply
 

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