2742. Painting the Walls

Difficulty:
Related Topics:
Similar Questions:

    Problem

    You are given two 0-indexed integer arrays, cost and time, of size n representing the costs and the time taken to paint n different walls respectively. There are two painters available:

    Return **the minimum amount of money required to paint the **n walls.

      Example 1:

    Input: cost = [1,2,3,2], time = [1,2,3,2]
    Output: 3
    Explanation: The walls at index 0 and 1 will be painted by the paid painter, and it will take 3 units of time; meanwhile, the free painter will paint the walls at index 2 and 3, free of cost in 2 units of time. Thus, the total cost is 1 + 2 = 3.
    

    Example 2:

    Input: cost = [2,3,4,2], time = [1,1,1,1]
    Output: 4
    Explanation: The walls at index 0 and 3 will be painted by the paid painter, and it will take 2 units of time; meanwhile, the free painter will paint the walls at index 1 and 2, free of cost in 2 units of time. Thus, the total cost is 2 + 2 = 4.
    

      Constraints:

    Solution

    /**
     * @param {number[]} cost
     * @param {number[]} time
     * @return {number}
     */
    var paintWalls = function(cost, time) {
        var dp = Array(cost.length).fill(0).map(() => Array(cost.length + 1));
        return helper(cost, time, 0, cost.length, dp);
    };
    
    var helper = function(cost, time, i, remains, dp) {
        if (remains <= 0) return 0;
        if (i === cost.length) return Number.MAX_SAFE_INTEGER;
        if (dp[i][remains] !== undefined) return dp[i][remains];
        var paintByPaidPainter = cost[i] + helper(cost, time, i + 1, remains - time[i] - 1, dp);
        var paintByFreePainter = helper(cost, time, i + 1, remains, dp);
        dp[i][remains] = Math.min(paintByPaidPainter, paintByFreePainter);
        return dp[i][remains];
    };
    

    Explain:

    Top down dp.

    Complexity: