Help with Dynamic Programming

Правка en1, от aakarshmadhavan, 2018-07-24 02:03:41

I am struggling very badly for recursive + cache/memoize solution. I read some solutions online and the idea is to start with the last balloon and work up. Here is the code for the solution:

class Solution {
    int [][] cache;
    public int maxCoins(int[] nums) {
        cache = new int[nums.length + 5][nums.length + 5];
        for(int [] arr : cache)
            Arrays.fill(arr, -1);
        return helper(nums, 0, nums.length - 1);
    }
    
    public int helper(int [] nums, int left, int right){
        if(right < left) 
            return 0;
        if(cache[left][right] != -1) 
            return cache[left][right];
        for(int i = left; i <= right; ++i){
            cache[left][right] = Math.max(cache[left][right], nums[i]*getVal(nums, left - 1)*getVal(nums, right + 1) + helper(nums, left, i - 1) + helper(nums, i + 1, right));  /////HELP ME HERE!
        }
        return cache[left][right];
    }
    
    public int getVal(int [] nums, int index){
        if(index < 0 || index >= nums.length) return 1;
        return nums[index];
    }
}

I am having the confusion in the Math.max line. What is it nums[i]*getVal(nums, left - 1)*getVal(nums, right + 1)?

I understand the nums[i] part, but I do not understand the right + 1 or the left - 1. Can someone please help explain it? I would appreciate it very much.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский aakarshmadhavan 2018-07-24 02:03:41 1490 Initial revision (published)