1269. Number of ways to stay in the same place after some steps

int LCS(string a, string b, string c, int n, int m, int k)
{
   vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(m + 1, vector<int>(k + 1, 0)));
   
   for(int s1 = 1;s1 <= n; s1++)
   {
       for(int s2 = 1;s2 <= m; s2++)
       {
           for(int s3 = 1;s3 <= k;s3++)
           {
               int inc = -1e9;
               if(a[s1 - 1] == b[s2 - 1] and a[s1 - 1] == c[s3 - 1])
               {
                   inc = 1 + dp[s1 - 1][s2 - 1][s3 - 1];
               }

               int *arr = new int[6];

               arr[0] = dp[s1 - 1][s2][s3];
               arr[1] = dp[s1][s2 - 1][s3];
               arr[2] = dp[s1][s2][s3 - 1];
               arr[3] = dp[s1 - 1][s2 - 1][s3];
               arr[4] = dp[s1 - 1][s2][s3 - 1];
               arr[5] = dp[s1][s2 - 1][s3 - 1];

               int maxi = -1e9;

               for(int i=0;i<6;i++)
               {
                   maxi = max(maxi, arr[i]);
               }

               dp[s1][s2][s3] = max(maxi, inc);
               delete arr;
           }
       }
   }
   
   return dp[n][m][k];
   
}

class Solution {
public:
    int solve(vector<int>& nums, int ops, int mask,vector<int>& dp){
        int m = nums.size(), n = (m/2);
        if(ops > n)
            return 0;
        if(dp[mask] != -1)
            return dp[mask];
        for(int i = 0 ; i < m; i++){
            if(mask & (1<<i))continue;
            for(int j = i + 1 ; j < m; j++){
                if(mask & (1<<j))continue;
                int newMask = (1<<i) | (1<<j) | mask;
                int score = ops*__gcd(nums[i], nums[j]) + solve(nums, ops+1, newMask, dp);
                dp[mask] = max(dp[mask], score);
            }
        }
        return dp[mask];
    }
    int maxScore(vector<int>& nums) {
        vector<int> dp(1<<14, -1);
        return solve(nums, 1, 0, dp);
    }
};

//This was my Solution
long long findMaxSubsetSum(int N, vector<int> &A) {
        // code here
        pair<long long,long long> prev, curr;
        if(N == 1)
            return A[0];
        prev = {A[N-1] , 0};
        for(int i = N - 2; i >= 0 ; i--){
            curr.first = max(A[i]+ prev.first, A[i] + prev.second);
            curr.second = prev.first;
            prev = curr;
        }
        return max(curr.first, curr.second);
        
    }
    //This is others solution
  // recursive -> O(2^n)
long long recursive_approach(vector<int>&arr,int index,int n){
    if(index>=n){
        return 0;
    }

    long long take,notTake;

    take=arr[index]+recursive_approach(arr,index+1,n);
    notTake=(index+1>=n?0:arr[index+1]+ recursive_approach(arr,index+2,n));

    return max(take,notTake);
}
 //memoized -> O(n), Space->O(n)
long long memoization_approach(vector<int>&arr,int index,int n,vector<int>&t){
    if(index>=n){
        return 0;
    }

    long long take,notTake;

    if(t[index]!=-1){
        return t[index];
    }

    take=arr[index]+memoization_approach(arr,index+1,n,t);
    notTake=(index+1>=n?0:arr[index+1]+ memoization_approach(arr,index+2,n,t));

    return t[index]=max(take,notTake);
}
//tabulation -> O(n), O(n)
long long tabulation_approach(vector<int>&arr,int n){
    vector<int>t(n+2,0);
    long long take,notTake;
    for(int i=n-1;i>=0;i--){
        take=arr[i]+t[i+1];
        notTake=(i+1>=n?0:arr[i+1]+t[i+2]);
        t[i]=max(take,notTake);
    }
    return t[0];
}
//optimal -> O(n) , O(1)
long long spaceOptimized_approach(vector<int>&arr,int n){
    long long take,notTake,prev_1,prev_2;
    prev_1=0;
    prev_2=0;

    for(int i=n-1;i>=0;i--){
        take=arr[i]+prev_1;
        notTake=(i+1>=n?0:arr[i+1]+prev_2);
        prev_2=prev_1;
        prev_1=max(take,notTake);
    }

    return prev_1;
}

// given two strings s1 and s2 (|s1| == |s2|) make s1 same as s2 using following 2 operations 
// 1. swap any two elements at indices i and j in s1 with cost x ,
// 2. swap two adjacent elements with cost 1
// achieve this with minimum cost 

 
#define pb push_back 

class Solution {
public:
    vector<double> dp;
    double findMin(vector<int>& diff, int i, int x){
        if( i == 0)
            return x / 2.0;
        if( i == -1)
            return 0;
        if(dp[i] != -1)
            return dp[i];
        double left  = findMin(diff, i-1, x) + x/2.0;
        double right = findMin(diff, i-2 , x) + diff[i] - diff[i-1];
        return dp[i] = min(left, right);
    }
    int minOperations(string s1, string s2, int x) {
        vector<int> diffs;
        int n = s1.length();
        for(int i = 0; i < n; i++)
            if(s1[i] != s2[i])
                diffs.pb(i);
        if(diffs.size() & 1)
            return -1;
        dp.resize(diffs.size(),-1);
        return (int)findMin(diffs, diffs.size() - 1, x);
        
    }
};
// Its O(n) time and O(n) space;

class Solution {
public:
	//assume you are standing at the ith index and you ask should I choose (i-1)th or (i-2)th to reach the ith position then choose whichever is lesser in cost.
	// ex - > [2,3,1,1,1,4,2,1,3]
	// we insert 0 at beginning and end
	// [0,2,3,1,1,1,4,2,1,3,0], n = 11
	//we start the iteration from 2nd index 
	// [0,2,_,_,_,_,_,_,_,_,_]
	// [0,2,3,_,_,_,_,_,_,_,_]
	// [0,2,3,3,_,_,_,_,_,_,_]
	// [0,2,3,3,4,_,_,_,_,_,_]
	// [0,2,3,3,4,4,_,_,_,_,_]
	// [0,2,3,3,4,4,8,_,_,_,_]
	// [0,2,3,3,4,4,8,6,_,_,_]
	// [0,2,3,3,4,4,8,6,7,_,_]
	// [0,2,3,3,4,4,8,6,7,9,_]
	// [0,2,3,3,4,4,8,6,7,9,7]
	// our answer is 7;

    int minCostClimbingStairs(vector<int>& cost) {
        cost.insert(cost.begin() + 0, 0);
        cost.push_back(0);
        vector<int> dp(cost);
        for(int i = 2; i < dp.size() ; i++)
            dp[i] = dp[i] + min(dp[i-1],dp[i-2]);
        return dp.back();
    }
};

class Solution {
public:
    const int m = 1e9+7;
    using vvi = vector<vector<int>>;
    int countWays(int idx, int steps, int arrLen,vvi& dp){
        if(idx < 0 || idx >= arrLen)    return 0;
        if(steps == 0)
            if(idx != 0)  return 0;
            else return 1;
        if(dp[idx][steps] != -1)
            return dp[idx][steps];
        return dp[idx][steps] = ((countWays(idx,steps-1,arrLen,dp)%m + countWays(idx+1,steps-1,arrLen,dp)%m )%m+ countWays(idx-1,steps-1,arrLen,dp)%m)%m;
    }
    int numWays(int steps, int arrLen) {
        vvi dp;
        arrLen = min(steps/2+1,arrLen);
        dp.resize(arrLen + 1,vector<int>(steps+1, -1));
        return countWays(0, steps, arrLen,dp);
    }
};

Conveyor.DecisionPoint current = ownerobject(c);
Object item = param(1);
Conveyor conveyor = param(2);
Conveyor.Item conveyorItem = conveyor.itemData[item];
/**send Item*/

// 1. send item by percentage
if(bernoulli(30, 1, 0)){
	Conveyor.sendItem(item, current.outObjects[1]);
}


// 2. send item by item type (label)
Array dpArray = current.outObjects.toArray();
//int itemType = item.Type;
for (int index = 1; index <= dpArray.length; index++){
	if(item.Type == index){
		Conveyor.sendItem(item, current.outObjects[index]);
	}
}

// 3. same as previous but shorter

Conveyor.sendItem(item, current.outObjects[item.Type]);

/**Reference and Control the conveyor item from the script*/
Conveyor conveyor = Model.find("DP23").as(Conveyor.DecisionPoint).conveyor;
Object enteringItem = Model.find("DP23").as(Conveyor.DecisionPoint).activeItem;
Conveyor.Item conveyorItem = conveyor.itemData[enteringItem];
applicationcommand("showconsole", CONSOLE_OUTPUT);
clearconsole;

// conveyor item properites
print(conveyorItem.entrySpace);
print(conveyorItem.movingSpace);
print(conveyorItem.currentDistance);
print(conveyorItem.destination);
print(conveyorItem.position);
print(conveyorItem.totalDistance);

// conveyor item methods=
conveyorItem.turn();
conveyorItem.stop();
conveyorItem.resume();

git reset 89f6c3d --hard

class Solution{
public:
    using vs = vector<string>; using um = unordered_map<string,bool>;
    void fun(int idx,um& dict, string& s, vs& ans,vs sentence, const int& n){
        if(idx == s.length()){
            string main;
            for(auto word : sentence)
                main += word + ' ';
            main.pop_back();
            ans.push_back(main);
            return;
        }
        string temp = "";
        for(int i = idx; i < s.length(); i++){
            temp.push_back(s[i]);
            if(dict[temp]){
                sentence.push_back(temp);
                fun(i+1, dict, s, ans, sentence, n);
                sentence.pop_back();
            }
        }
    }
    vector<string> wordBreak(int n, vector<string>& d, string s)
    {
        // code here
        um dict;
        for(auto word : d)
            dict[word] = true;
        vs ans;
        vs sentence;
        fun(0, dict, s, ans, sentence, n);
        return ans;
    }
};