Important problems from Partition DP | MUST DO

MUST DO PROBLEMS:-
1) https://leetcode.com/problems/minimum-cost-to-cut-a-stick/
2) https://leetcode.com/problems/number-of-ways-to-divide-a-long-corridor/

1) Given a wooden stick of length n units. The stick is labelled from 0 to n. For example, a stick of length 6 is labelled as follows:
Given an integer array cuts where cuts[i] denotes a position you should perform a cut at.
You should perform the cuts in order, you can change the order of the cuts as you wish.
The cost of one cut is the length of the stick to be cut, the total cost is the sum of costs of all cuts. When you cut a stick, it will be split into two smaller sticks (i.e. the sum of their lengths is the length of the stick before the cut). Please refer to the first example for a better explanation.
Return the minimum total cost of the cuts.

Example 1:
Input: n = 7, cuts = [1,3,4,5]
Output: 16
Explanation: Using cuts order = [1, 3, 4, 5] as in the input leads to the following scenario:
The first cut is done to a rod of length 7 so the cost is 7. The second cut is done to a rod of length 6 (i.e. the second part of the first cut), the third is done to a rod of length 4 and the last cut is to a rod of length 3. The total cost is 7 + 6 + 4 + 3 = 20.
Rearranging the cuts to be [3, 5, 1, 4] for example will lead to a scenario with total cost = 16 (as shown in the example photo 7 + 4 + 3 + 2 = 16).

Example 2:
Input: n = 9, cuts = [5,6,1,4,2]
Output: 22
Explanation: If you try the given cuts ordering the cost will be 25.
There are much ordering with total cost <= 25, for example, the order [4, 6, 5, 2, 1] has total cost = 22 which is the minimum possible.

Constraints:
2 <= n <= 10^6
1 <= cuts.length <= min(n - 1, 100)
1 <= cuts[i] <= n - 1
All the integers in cuts array are distinct.

------------------------------------------------------------------------------------------------------------------------------------

2) Along a long library corridor, there is a line of seats and decorative plants. You are given a 0-indexed string corridor of length n consisting of letters 'S' and 'P' where each 'S' represents a seat and each 'P' represents a plant.
One room divider has already been installed to the left of index 0, and another to the right of index n - 1. Additional room dividers can be installed. For each position between indices i - 1 and i (1 <= i <= n - 1), at most one divider can be installed.
Divide the corridor into non-overlapping sections, where each section has exactly two seats with any number of plants. There may be multiple ways to perform the division. Two ways are different if there is a position with a room divider installed in the first way but not in the second way.
Return the number of ways to divide the corridor. Since the answer may be very large, return it modulo 109 + 7. If there is no way, return 0.

Example 1:
Input: corridor = "SSPPSPS"
Output: 3
Explanation: There are 3 different ways to divide the corridor.
The black bars in the above image indicate the two room dividers already installed.
Note that in each of the ways, each section has exactly two seats.

Example 2:
Input: corridor = "PPSPSP"
Output: 1
Explanation: There is only 1 way to divide the corridor, by not installing any additional dividers.
Installing any would create some section that does not have exactly two seats.

Example 3:
Input: corridor = "S"
Output: 0
Explanation: There is no way to divide the corridor because there will always be a section that does not have exactly two seats.

Constraints:
n == corridor.length
1 <= n <= 10^5
corridor[i] is either 'S' or 'P'.

---------------------------------------------------------------------------------------------------------------------------------------

1)
class Solution {
public:
    vector<vector<int>> dp;

    int helper(vector<int> &cuts, int start, int end){
        if(start+1>=end){
            return 0;
        }
        if(dp[start][end]!=-1){
            return dp[start][end];
        }
        int res=INT_MAX;
        for(int k=start+1;k<end;k++){
            int cost=abs(cuts[end]-cuts[start])+helper(cuts,start,k)+helper(cuts,k,end); // when cut up at index k
            res=min(res,cost);
        }
        return dp[start][end]=res;
    }

    int minCost(int n, vector<int>& cuts) {
        sort(cuts.begin(),cuts.end());

        cuts.insert(cuts.begin(),0);
        cuts.push_back(n);

        dp.resize(cuts.size()+1,vector<int>(cuts.size()+1,-1));

        return helper(cuts,0,cuts.size()-1);
    }
};

------------------------------------------------------------------------------------------------------------------------------------

2)

class Solution {
public:
    long long dp[100001][3];

    int helper(string &corridor, int curr, int seats){
        int n=corridor.size();
        if(curr==n){
            return seats==2;
        }
        if(dp[curr][seats]!=-1){
            return dp[curr][seats];
        }
        if(seats==2){
            if(corridor[curr]=='P'){
                int TAKE_PLANT=helper(corridor,curr+1,seats)%1000000007;  // DO NOT PARTITION YET
                int DO_NOT_TAKE_PLANT=helper(corridor,curr+1,0)%1000000007; // PARTITION RIGHT HERE
                return dp[curr][seats]=(TAKE_PLANT+DO_NOT_TAKE_PLANT)%1000000007;
            }
            else{
                return dp[curr][seats]=helper(corridor,curr+1,1)%1000000007; // PARTITION NOW, seat will be 1, current seat part of next segment
            }
        }
        else{
            if(corridor[curr]=='S'){
                seats++;
            }
            return dp[curr][seats]=helper(corridor,curr+1,seats)%1000000007; // maintain seats
        }
    }
    int numberOfWays(string corridor) {
        memset(dp,-1,sizeof(dp));
        return helper(corridor,0,0);
    }
};  //RECURSION+MEMO(ACCEPTED BUT SLOW)


/*
class Solution {
public:
    int numberOfWays(string corridor) {
        vector<int> seats;
        int n = corridor.size();
        long long ans = 1, mod = 1e9+7;
        for(int i = 0; i < n; i++) {
            if(corridor[i]=='S'){
                seats.push_back(i);
            }
        }

        if(seats.size() % 2 == 1 or seats.size() == 0) {
            return 0;
        }

        for(int i = 2; i <= seats.size()-2; i += 2) {
//leaving first two seats and last two seats as they are neccessary and no partition between them
            ans = (ans % mod * (seats[i] - seats[i-1]) % mod) % mod;
        }

        return ans;
    }
};  //GREEDY BUT O(N)SPACE
*/

/*
class Solution {
public:
    int numberOfWays(string s) {
        long ways=1;
        int seats=0;
        int plants=0;
        for(auto e: s){
            if(e=='S'){
                if(seats==2){
                    ways= ways*(plants+1)%1000000007;
                    seats=plants=0;
                }
                seats++;
            }
            else if(seats==2) plants++;
        }
        return seats==2 ? ways : 0;
    }
};*/  //GREEDY BUT O(1)SPACE