Knowledge Base | Daily Notes

Striver series

Aug 30, 20244 min read

DP 1

  • Those who don’t remember the past are condemned to repeat it
  • task Q. Why is DP2 video missing from playlist?
  • task Q. What is the name of the author?
  • First author will tell Recursion andtabulation for same.
  • How ismemoizationTop_Down ?
  • Author is emphasizing on use oftabulation with space optimization.
  • lecture 6 and 7 of highest importance.
  • Fibonacci equation to recursive function
  • The equation is basically returned from the function andbase_case has to be decided.
  • To get base case first ensure the limit, for f(-1) not possible so f(0) = 1, this is base case
  • First f(4) will complete, then f(3) will be picked.
  • f(4) also has f(3) so this isoverlapping_subproblems
  • memoization array will be 1D or 2D depends on the number of parameters.
  • Fibonacci with Dynamic programming, andmemoization
  • tabulation means try to go frombase_case to required answer, so for Fibonacci, instead of starting with 5, will start from 0.
  • We create dp array similar to inmemoization fortabulation and start by filling the base conditions.
  • So for Fibonacci dp[0] = 0 and dp[1] = 1
  • Convert returned statement in table form,
  • Stack space not required now, sotabulation had betterspace_complexity
  • Raj Vikramaditya is getting to use only last two solutions to reducespace_complexity from n to 1, eg
  • teaching_tips, Compare with examples Target audience already knows.

DP3 Frog Jump

DP5- Maximum sum of non-adjacent elements (House robber)

DP_1D_Array

  • Try out all subsequences and select the maximum one.
  • House Robber

DP6 (IMPORTANT)

DP7 (IMPORTANT)

DP 41 Longest Increasing Subsequence

Recursion series

L6 Recursion on Subsequence

  • For { 3, 2, 1 } there will be 8 subsequences

  • Intuition is that we can either take an element or not take it.

  • base_case if index is greater than length of array print empty array and return.

  • Memorize below till the end of your 🎲

    • carriedList.add(arr[i])
    • func(i + 1, carriedList) (case of pick)
    • carriedList.remove(arr[i])
    • func(i + 1, carriedList) (case of not pick)

  • Remove is used so various combinations of array can be passed to function.

  • Program

  • What is not pick? Ans.

  • With not pick condition in front:

  • time_complexity 2

  • Here is the Javascript code I wrote for same, below is increasive recursion, the base condition value breaks the loop when the index reaches the array length. At this point therecursion_tree starts returning the value and starts going up the tree.

function allSubsequences(index, tempArr, arr, n) {
    if (index == n) {
        console.log(tempArr);
        return;
    }
 
    tempArr.push(arr[index]);
    allSubsequences(index + 1, tempArr, arr, n);
    tempArr.pop();
    allSubsequences(index + 1, tempArr, arr, n);
}
 
let arr = [3, 1, 2];
let tempArr = [];
allSubsequences(0, tempArr, arr, arr.length)

L7 Printing subsequence with sum k

  • pick and not-pick
  • Carry the index, the array and sum
 
function findRequiredSum(index, tempArr, sum, requiredSum, arr, n) {
 
	if (index == n) {
		if (sum == requiredSum) {
			console.log(tempArr);
			return true;
		}
		return false;
	}
 
	tempArr.push(arr[index]);
	sum += arr[index];
	if (findRequiredSum(index + 1, tempArr, sum, requiredSum, arr, n)) {
		return true;
	};
	sum -= arr[index];
	tempArr.pop();
		if (findRequiredSum(index + 1, tempArr, sum, requiredSum, arr, n)) {
		return true;
	}
	return false;
}
 
let arr = [1, 2, 1];
let requiredSum = 2;
let tempArr = [];
 
findRequiredSum(0, tempArr, 0, requiredSum, arr, arr.length); // 6 params
  • What isstriver telling now after explaining the solution?
  • Don’t use global variables, use 6. Functional Programming instead which is basically pass the params in functions.
  • if we are getting a result break the recursion.
  • Memorize above technique.
  • Why is he changing code now?

Re.5 Notes

Graph View

Backlinks