Mastering critical SKILLS in Algorithms using C++: Part 2

Explain the knapsack problem with weights and values, a capacity constraint, and a goal to maximize value, using dynamic programming while contrasting brute force and recursion with binary masks.

Explore recursive backtracking to generate all subsets as 2^N masks, tracing a depth-first approach and preparing for dynamic programming in later sections.

See how dynamic programming solves the knapsack problem by moving from brute force to memoized recursion, defining a dp with index and remaining weight, and detailing choices and base cases.

Explore the knapsack problem through recursive choices: take or skip. Build a dynamic programming solution by defining index and remaining weight, deriving a two-substate recurrence with the pick-or-leave pattern.

Implement a classic knapsack problem in c++ with weight and value vectors, using memoized recursion to achieve time and space proportional to nw, with skip or take choices.

Explore dynamic programming for the LIS, distinguishing subsequences from subarrays and using a pick-or-leave approach with index and previous index states to ensure optimal substructure and overlapping subproblems.

Discover a dynamic programming solution for the LIS problem 2, using a memory array and two choices to pick or skip. The approach mirrors knapsack, achieving O(n^2) time.

Explore dynamic programming for the LIS problem using a subarray perspective, defining LIS(index) with required elements, brute-forcing valid next choices in overlapping subproblems, and building a knapsack-like DP framework.

Explore a 1d-memory dynamic programming approach to LIS, computing LIS from each start and combining results into a full sequence.

Explore the longest common subsequence problem for two strings, using brute force and the pick-or-leave pattern, and formulate LCS(i, j) with base cases and dynamic programming insights.

Explore the LCS implementation using a 2d memory table with indices i and j, handling base cases and matches, and using max of (i+1, j) and (i, j+1) for mismatches.

Master dynamic programming for three medium challenges: subset sum, partition equal subset, and stacking cuboids via rearrangement. Apply knapsack-like thinking and LIS-based ideas to maximize height.

Explore the subset sum dp problem with a pick-or-leave approach, recursion and pruning, then reduce it to partitioning into equal halves using the same code.

Sort every cuboid’s three dimensions, then sort the cuboids and apply the longest increasing subsequence to maximize stack height. Pre-processing enables this approach, with a topological-sort alternative noted.

Tackle dynamic programming challenges: maximize robberies on non-adjacent houses, optimize stock trading with cooldown and zero or one stock, and transform arrays into mountain shapes using LIS insights.

Solve the second homework by applying dynamic programming to a knapsack-like, single-constraint house robbery problem, deciding to skip or pick each house and jump to the next.

Explore dynamic programming for a stock buy-sell problem by defining a 3-state model (nothing, buy, sell) with 0/1 stock across indices, and master pick-or-leave decisions and state transitions.

Reframe the problem to keep the maximum elements forming a mountain. Compute LIS ending at each index and LDS starting at each index, then maximize LIS[i] + LDS[i] - 1.

Master the edit distance problem (Levenshtein) with a recursive solution using insert, delete, and change to minimize cost, and explore its link to LCS with memoization for overlapping subproblems.

Master edit distance by implementing its base cases and three options—change, deletion, and insertion—then take the minimum across calls, mirroring LCS and illustrating forward and backward code.

Use dynamic programming to maximize the product when splitting a non-negative n into k positive integers. Define F(n), loop over first splits, and handle 2 and 3 as special cases.

Implement integer break with dynamic programming in C++. Handle base cases n=1, 2, 3, then try splits 1..n-1 to maximize the result, using linear memory and O(N^2) time.

Solve two dynamic programming challenges: determine the minimum cost to traverse a cost array with jumps, paying each touched cell, and break n into the fewest perfect squares.

We solve the dp homework by modeling two states with moves of +1 or +2 to minimize the result, and generate perfect squares to compute the sum.

Explains range pattern problems with two indices on a string, using memoization to precompute palindromic substrings in O(n^2) time and answer queries in time, then applies to longest palindromic substring.

Identify the consecutive range pattern in arrays to split input into blocks with a cost to minimize, and apply a lis-style dynamic program to find the optimal subarray splits.

Explore the nested range pattern and how top-level understanding switches to bottom-up evaluation for parenthesizing expressions. Learn matrix chain multiplication and how optimal splits minimize operation cost.

Apply the nested range pattern to matrix chain multiplication, using range splits and preprocessing of rows and columns to minimize split costs via recursion.

Master dynamic programming with three medium challenges: shelf layout to minimize height under width, partitioning arrays with at most k, and palindrome insertions to make strings palindromes.

Explore dynamic programming for three problems: splitting arrays into valid consecutive ranges under shelf width, calculating range penalties, and inserting characters to form a palindrome.

tackle two hard dynamic programming challenges: the minimum cost to cut a stick with given cuts, and the burst balloons problem, seeking maximum coin gain via optimal bursting order.

Apply a backward dynamic program for nested ranges by picking the last balloon, separating left and right subproblems, and using a recurrence with added boundaries, O(N^3), like MCM.

Explore how dynamic programming counts decoding ways, handling base cases, overflow with modulo, and duplicates, using the A=1 to Z=26 mapping and the 226 example.

Learn to count palindromic subsequences by removing characters with dynamic programming, handle duplicates in the recurrence for equal or different ends, and treat the empty string outside the recurrence.

Explore dynamic programming through four medium challenges: coin change counting with combinations and permutations, dice sum problems with modulo, and product-based binary trees.

Explore the coin change homework as an unlimited item reuse subset problem, using a recursive f(index, target) where leaving advances the index and picking stays on the same index.

Explore a dynamic programming approach to the combination sum where order matters, drop the index, and iterate over all numbers with target-based dp to allow repeats.

Apply dynamic programming with brute-force exploration of dice faces, tracking index and target state, and apply modulus early to prevent overflow in C++.

Count possible binary trees from given leaves using dynamic programming and the product rule. Use memoization, divisors from the input, and long long arithmetic with mod to prevent overflow.

Explore the dynamic programming pattern on grids by treating the grid as a DAG, and count unique paths from top-left to bottom-right with obstacles using a cntWays DP recurrence.

Master dynamic programming on grids by solving a minimum-cost path from first to last row. Explore problems: three-direction paths, four-direction exits, largest square of ones, and minimum health.

Develop dynamic programming for grid paths from any first-row cell with three move options, using a depth trick on (row, column, moves) to prevent cycles and guard overflow with modulus.

Model the problem with dp[i][j] as the largest square of ones ending at (i, j); use the minimum of the top, left, and diagonal, plus one, to obtain the maximum.

Create a print function that uses the existing dynamic programming result to output the longest increasing subsequence without altering the dp, by comparing each choice to the optimal value.

Explore dynamic programming outputs with lis reconstruction, edit distance printing focusing on first string changes, and bracketed matrix multiplication sequences, through practical medium challenges.

Learn to print dynamic programming results by reconstructing optimal choices for LIS, edit distance, and matrix chain multiplication. Master handling base cases, path tracing, and bracketed output.

Explore the transition from memoization and recursion to bottom-up tabulation, building dp states from base cases with careful loop order and verification.

Learn to implement LIS tabulation by converting memoization to a forward, bottom-up approach. Rewrite LIS from end to start, then build the table from 0 to size-1 with base memory[0]=1.

Explore LIS tabulation from base cases to building sequences, then optimize with binary search to achieve n log n by replacing the first greater value to keep future options.

Demonstrates converting a pick-or-leave LIS memoization approach to tabulation with i and prev states, forward and backward loops, and careful no-previous value handling.

Explore counting coin change with infinite coins, and convert a recursive memoization approach into efficient tabulation using two loops and base-case handling.

Learn memory-optimized coin change tabulation by using two rows to reduce space from O(NM) to O(M), flipping between cache and current and focusing on last two states.

Convert classic problems to tabulation, starting from backward memoization and rewriting recursive code before tabulation. Tackle edit distance, filling bookcase shelves, dice rolls, and out of boundary paths problems.

Explore dp tabulation by building i and j states from small to large, applying base cases, and solving minDistance, shelves, and count ways problems with an answer function.

Explore DP tabulation for hard challenges: minimum swaps to make two sequences strictly increasing, the nth ugly number, and the longest wiggle subsequence, with memory optimizations to O(n) and O(1).

Explore a maze backtracking example in C++, using a grid and a global variable to count all paths from the top-left to the bottom-right, marking visited cells.

Trace maze code using backtracking by marking visited grid cells with z and undoing moves, exploring paths via recursion and shared state, and compare complexity to Catalan-based cases.

Extend backtracking to count only shortest paths in a maze. Define best path length and total shortest paths, update during backtracking, and undo steps to keep the minimum path.

Apply backtracking to partition an array into k equal-sum subsets, analyzing partition and numbers perspectives, verifying divisibility, and recursively assigning numbers to partitions.

Implement a backtracking approach to partition an array into k groups with equal sum, tracking current partition sums and a two-dimensional printing structure while exploring and undoing choices.

Explore a two-level backtracking approach to partition an array into k subsets using a dynamic programming inspired subset selection and recursion from index 0 after each subset.

Backtrack to partition numbers into k subsets using a boolean array to mark selected numbers and a printing array for partitions, guided by three base cases and a pick-or-leave recursion.

Tackle medium to hard backtracking and recursion challenges, including graph path enumeration, N-Queens, Sudoku, permutations, and Tower of Hanoi, paired with coding tips and recursion insights.

Apply backtracking to enumerate all paths from the source to the target in a DAG, using recursion, path construction, and backtracking steps to collect each solution.

Apply backtracking to solve the N-Queens problem by row-by-row queen placement, using boolean arrays for columns and diagonals and index formulas r+c and r-c to prune conflicts.

Demonstrates a sudoku solver using backtracking on a 9x9 grid, iterating empty cells and trying digits 1–9 with a canPlace check across rows, columns, and blocks.

Explore generating all permutations via backtracking with a swap trick, recursing from an index to the end and printing results in lexical order.

Use a frequency array to handle duplicates in permutation generation with backtracking. Build a dictionary of frequencies (unordered_map), pick a value, place it, decrement, recurse, and undo on return.

Solve the Tower of Hanoi using a recursive what-not how policy approach, moving the top n-1 disks, then the last disk, then n-1 again, and analyze time complexity via substitution.