Performance lesson from Leetcode 1770. Maximum Score from Performing Multiplication Operations

Excellent performance lesson I’ve got today from leetcode challenge: I’ve created correct algo to solve 1770. Maximum Score from Performing Multiplication Operations during context but wasn’t able to get it to pass Time Limit during the context, no score for me today :(

My solution was based on simple backtracking and recursion, let’s pick the max between:

• nums[l] * multiplicator[i] + F(l+1, r, i+1)
• nums[r] * multiplicator[i] + F(l, r-1, i+1)

To cache result I used Map where String key was formed as l+”.”+r

class Solution {
    Map<String, Integer> cache = new HashMap<>();
    
    public int maximumScore(int[] nums, int[] multipliers) {
        int l = 0, r = nums.length-1;
        int score = 0;
        
        return dfs(nums, multipliers, l ,r, 0);
    }  
    
    int dfs(int[] nums, int[] multipliers, int l, int r, int k) {
        if(k >= multipliers.length) return 0;
        if(cache.containsKey(l+"."+r)) return cache.get(l+"."+r);
              
        int res = Math.max(
            multipliers[k] * nums[l] + dfs(nums, multipliers, l + 1, r, k+1),
            multipliers[k] * nums[r] + dfs(nums, multipliers, l, r - 1, k+1)
        );
        cache.put(l+"."+r, res);
        return res;
    }
    
}

Bum! Time limit exceed, while I tried reimplement using DP, the context time run out. DP is my weak spot, can we still avoid it? This has happened to me 2nd time!

However, experimenting with backtracking after context, I found amazing thing: if we use Map<Integer, Map<Integer, Integer>> where left most intrval points to a list of right most intervals with found values — it works! performance is better vs composite key:

class Solution {
    Map<Integer, Map<Integer, Integer>> cache = new HashMap<>();
    
    public int maximumScore(int[] nums, int[] multipliers) {
        int l = 0, r = nums.length-1;
        int score = 0;
        
        return dfs(nums, multipliers, l ,r, 0);
    }  
    
    int dfs(int[] nums, int[] multipliers, int l, int r, int k) {
        if(k >= multipliers.length) return 0;
        if(cache.containsKey(l) && cache.get(l).containsKey(r)) return cache.get(l).get(r);
              
        int res = Math.max(
            multipliers[k] * nums[l] + dfs(nums, multipliers, l + 1, r, k+1),
            multipliers[k] * nums[r] + dfs(nums, multipliers, l, r - 1, k+1)
        );
        if(!cache.containsKey(l)) cache.put(l, new HashMap<>());
        cache.get(l).put(r, res);
        return res;
    }
    
}