Welcome back to our daily leetcode problem.

Today we will solve the problem 1578: Minimum Time to Make Rope Colorful.

Link Problem

Solution:

• Using recursive to solve this.

• For every state, check if current colors is different from the previous color.

• If not, then we will change the current colors, and the result will be the minTime of change.

• else, we can just simply go to the next colors and process it.

TC: O(n)

Code:

class Solution {
public:

    int solve(string &colors, vector<int>& neededTime, char previous, int minTime, int n) {
        if(n < 0) {
            return 0;
        }
        int ways = 0;

        if(colors[n] != previous) {
            ways = solve(colors, neededTime, colors[n], neededTime[n], n - 1);;
        } else {
            ways = solve(colors, neededTime, colors[n], max(neededTime[n], minTime), n - 1) +
                min(neededTime[n], minTime);
        }

        return dp[n] = ways;
    }

    int minCost(string colors, vector<int>& neededTime) {
        const int n = (int) colors.size();
        return solve(colors, neededTime, '&', neededTime[n - 1], n - 1);
    }
};