47. Partition dp | DP on squares

 It is used when there are multiple ways to solve & we want to choose the best way
e.g., Matrix multiplication in A(BC) or (AB)C

we will be given an array & we can solve array by choosing any partition dividing array into 2 parts
i.e., (i to k) & (k+1 to j)

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

MCM-(theory)

total ops = R1*C1*C2
since 2 matrices can be multiplied only if C1=R2
Ques- given matrix dimensions, tell min ops reqd to do MCM

1. start with entire array and represent them with i (start point) & j (end point)

2. Run a loop to try all partitions

3. Return best possible partitions

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

1. MCM-

time: O(n3)

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

Tabulation- important thing here is what will be the ranges of i and j loops in bottom to up approach

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

2. min cost to cut stick-

(non intuitive)

for sub problems to be solved independently we have to sort the cuts array

we will append 0 and total length of stick at start and end of cuts array

so here, i starts from 1 and j from n-1

cost for a cut at idx = cuts[j+1] - cuts[i-1] + f (i,idx-1) + f (idx+1,j)

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

3. Burst Balloons-

we cannot individually solve subproblems formed if partition is done

so we will solve in reverse manner like for every array we will see who can be the last guy

below pic tells why subproblems are independent of each other-

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

4. no. of ways to parse expression to true-

at every operator ( &, |, ^ ) we can do partition 

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

so for each sub problem i need to determine ways in which it can be true and similarly ways in which it can be false;

BASE-CASE:

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

5. Palindrome partitioning-2

(front partition- new DP concept)

we will do a partition at index i only if string till index i is palindromic

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

6. Partition array for max sum-

(front partition)

here, f(i)= max sum u can generate starting from index i

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

Generally in square problems, we tend to write tabulation solution as it is more intuitive

7. Maximal Rectangles

Pre- requisite: 

area of largest rectangle in histogram (stack)

-----------------------------------
soln- done in stack playlist notes

this ques falls into dp as instead of a prefix matrix we use a single vector storing heights till curr row , like it is memoizing previous values

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

8. Count Square Submatrices with all 1s-

1. create dp matrix where each element dp[i][j] tells no. of squares whose right bottom is at (i,j)

2. row 0 & col 0 will be same as og matrix

3. fill the dp table

4. sum of all elements of dp table is ans

-----------

filling up dp table-

except row 0 and col 0, for each element in matrix value is 1 + min( {i-1,j}, {i-1,j-1}, {i,j-1} )

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

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