notes.txt

//memo
if(i == n) ret 0

check vis
if dp[i][pi+1] != -1 ret dp[i][pi+1]
//not take
int len  = 0 + f(arr,n,i+1,pi,dp)

if(pi == -1 || arr[i]>arr[pi])
	//take
 	len = max(len, 1+ f(arr,n,i+1,i,dp))

return dp[i][pi+1] = len;

//tab
//do not need base case
int[][] dp = new int[n+1][n+1]

for(int i = n-1, i >= 0, i--)
	for(int pi = i-1, pi >= -1, pi--)
		int len  = 0 + dp[i+1][pi+1]

		if(pi == -1 || arr[i]>arr[pi])
			//take
 			len = max(len, 1+ dp[i+1][i+1])

return dp[i][pi+1] = len;

//space opt
//at all the i make it current, at all i+1 make it next

int[] curr = new int[n+1]
int[] next = new int[n+1]

for(int i = n-1, i >= 0, i--)
	for(int pi = i-1, pi >= -1, pi--)
		int len  = 0 + next[pi+1]

		if(pi == -1 || arr[i]>arr[pi])
			//take
 			len = max(len, 1+ next[i+1])

return curr[pi+1] = len;


-------------------------LCS------------------------------------------------------
LCS - RECURSION
f(i1,i2)
	//base
	if(i1<0 || i2<0)
		return 0

	//match
	if(sa[i1] == sb[i2])
		return 1 + f(i1-1,i2-1)

	//not match
	else
		return 0+ max(f(i1-1,i2), f(i1,i2-1))

//memo
f(s1,s2,i1,i2.int[][]dp)
	if(i1<0 or i2<0)
		return 0
	//visited subproblem
	if(dp[i1][i2] != -1)
		return dp[i1][i2]
	
	//match
	if(s1.charAt(i1) == s2.charAt(i2))
		return dp[i1][i2] = 1 + f(s1,s2,i1-1,i2-1,dp)

	else
		//not match
		return dp[i1][i2] = 0 + max(f(s1,s2,i1-1,i2,dp),f(s1,s2,i1,i2-1,dp));

lcs(s1,s2)
	int n = len(s1)
	int m = len(s2)
	int[][] dp = new int[n][m]
	for(int rows[]: dp)
		Arrays.fill(rows,-1);
	return f(s1,s2,n-1,m-1,dp);

//tabulation - eliminate the auxx stack space by using nested for loops and discarding the 
recursion tree
//tab -> bottom up
//base case will be altered 
// recurrence will be same but instead in for loops 

a|e
0 0

i1-1 -> 0-1 -> -1-> recursion is over 
recursive code ->       -1, 0, 1, 2,.....,n
tab will co-ord shift -> 0. 1, 2, 3......,n+1

so now to alter base case-> simply do i1==0 or i2==0 then return 0
ie. dp[i1][0] = 0
ie. dp[0][i2] = 0

//tab code
lcs(s1,s2)
	int n = len(s1)
	int m = len(s2)
	int[][] dp = new int[n+1][m+1]
	for(int rows[]: dp)
		Arrays.fill(rows,-1);

	//base case as discussed
	for(int i=0, i<=n;i++)
		dp[i][0] = 0
	for(int i=0; i<=m; i++)
		dp[0][i] = 0

	//main logic
 	//since 0 is covered in base case start from 1
	for(int i1=1; i1<=n; i1++)
		for(int i2=1; i2<=m; i++)
			//match
			if(s1.charAt(i1-1) == s2.charAt(i2-1))
				dp[i1][i2] = 1 + dp[i1-1][i2-1];

			//not match
			else
				dp[i1][i2] = 0 + max(dp[i1-1][i2],dp[i1][i2-1]);

	return dp[n][m]


//space opt
dp[i1-1] to prev
dp[i1] to curr

lcs(s1,s2)
	int n = len(s1)
	int m = len(s2)
	int prev[] = new int[m+1]
	int curr[] = new int[m+1]

	//main logic
 	//since 0 is covered in base case start from 1
	for(int i1=1; i1<=n; i1++)
		for(int i2=1; i2<=m; i++)
			//match
			if(s1.charAt(i1-1) == s2.charAt(i2-1))
				curr[i2] = 1 + prev[i2-1];

			//not match
			else
				curr[i2] = 0 + max(prev[i2],curr[i2-1]);
		//since we need to update prev to curr for next iterations
		prev = (int[])(curr.clone());
	return prev[m] or curr[m]
	
----------------------------------------EDIT DISTANCE-----------------------------------------

	




			
	
recr
def md(self,w1,w2):
	if not w1 and not w2:
		return 0
	if not w1:
		return len(w2)
	if not w2:
		return len(w1)
	if w1[0] == w2[0]:
		return self.md(w1[1:],w2[1:])

	insert = 1 + self.md(w1, w2[1:])
	delete = 1 + self.md(w1[1:],w2)
	replace = 1 + self.md(w1[1:]+w2[1:])

	return min(insert,delete,replace)

//convert thus recr into memo
def md(self,w1,w2,i,j,memo):
	if i == len(w1) and j == len(w2):
		return 0
	if i == len(w1):
		return len(w2)-j
	if j == len(w2):
		return len(w1) - i

	if i,j not in memo:
		if w1[i] == w2[j]:
			ans = self.md(w1,w2,i+1,j+1,memo)
		else:
			insert = 1 + self.md(w1,w2,ij+1,memo)
			delete = 1 + self.md(w1,w2,i+1,j,memo)
			replace = 1 + self.md(w1,w2,i+1,j+1,memo)
			ans = min(insert,delete,replace)
		memo[(i,j)] = ans
	return memo[(i,j)]

//tabulation
def md(self,w1,w2):
	m = len(w1)
	n = len(w2)
	tbl = [[0]*(n+1) for _ in range(m+1)]

	for i in range(m+1):
		tbl[i][0] = i
	for j in range(n+1):
		tbl[0][j] = j

	for i in range(1,m+1):
		for j in range(1,n+1):
			if w1[i-1] == w2[j-1]:
				tbl[i][j] = tbl[i-1][j-1]
			else:
				tbl[i][j] = 1 + min(tbl[i][j-1], tbl[i-1][j], tbl[i-1][j-1])
	return tbl[-1][-1]


------------------------------------------------------MAX SUM INCR SUBSEQ [MSIS]-----------------------------------------------------------
//tab
//bottm up
int f(int[] arr, int n)
	//init 
	int i;
	int j;
	int max = 0;
	
	//init table
	int[] msis = new int[n];
	
	//fill msis with arr[i]
	for(int i = 0; i < n; i++)
		msis[i] = arr[i];
		
	//calc max sum values in bottom up fashion
	for(int i = 1; i < n ; i++)
		for(int j = 0; j< i; j++)
			if(arr[i] > arr[j] && msis[i] < msis[j] + arr[i])
				msis[i] = msis[j] + arr[i]
				
	//pick max of all msis vals
	for(int i = 0; i < n; i++)
		if(msis[i] > max)
			max = msis[i];
			
	return max;
	
---------------------------------------------MINIMUM PATH SUM-----------------------------------------------
min-path sum

//recr
f(i,j)
	//base case
	if(i==0 && j==0) return matx[0][0]

	//idx out of bnd
	if(i < 0 || j < 0) return INT_MAX(1e9)

	//main logic - directions -> UP , LEFT
	up = matx[i][j] + f(i-1,j)

	left = matx[i][j] + f(i, j-1)

	return min(up,left)

//memo
//create a dp array of size nm
//check if visited subproblem
//if visited return
//if not visited find answer and update value in dp

f(i, j, int[][] matx, int[][]dp)
	//base case
	if(i == 0 && j==0) return matx[0][0]

	//edge case - out of boundary
	if(i<0 || j<0)
		return (int) Math.pow(10,9);

	//check if problem is visited the  return val
	if(dp[i][j] != -1) return dp[i][j]

	//not visited -> go up and left
	int up = matx[i][j] + f(i-1,j,matx,dp);
	int left = matx[i][j] + f(i,j-1,matx,dp);

	return dp[i][j] = Math.min(up,left);

minpth(int n, int m, int[][]mtx)
	int[][] dp = new int[n][m];
	for(int row[]: dp)
		Arrays.fill(row,-1)
	return f(n-1,m-1,mtx,dp);

tc - o(mn)
sc - o(m-1)+o(n-1)+ o(nm)DP

//convert memo to tabln for eliminating ass 
minpth(n,m,int[][]mtx)
	int dp[][] = new int[n][m]
	
	for(int i=0; i<n; i++)
		for(int j=0; j<m; j++)
			if(i==0 && j==0) -> dp[i][j] = mtx[i][j]
			else
				int up = mtx[i][j]
				if(i>0) up += dp[i-1][j]
				else up+= (int)Math.pow(10,9)

				int left = mtx[i][j];
				if(j>0) left+= dp[i][j-1]
				else left += (int) Math.pow(10,9)

				dp[i][j] = Math.min(up,left)



	return dp[n-1][m-1]

//space opt
//place prev ipo dp[i-1] and curr ipo dp[i]
minpth(int n, int m, int[][] mtx)
	int prev[] = new int[n]
	for(int i=0; i<n; i++)
		int curr[] = new int[m];
		for(int j=0; j < m; j++)
			if(i==0 && j==0) curr[j] = mtx[i][j];

			else
				int up = mtx[i][j]
				if(i>0) up += prev[j]
				else up += (int) Math.pow(10,9)

				int left = mtx[i][j]
				if(j>0) left += curr[j-1];
				else left += (int) Math.pow(10,9);


				curr[j] = Math.min(up,left);

         	rev  = curr;

	return prev[m-1]