Dynamic Programming

Maximize total value of items in knapsack with capacity W. Items are either completely included or excluded (0/1 property). Solve using simple recursion.

Use recursion with memoization (top-down DP) to solve 0/1 Knapsack efficiently by avoiding repeated work of overlapping subproblems.

Solve 0/1 Knapsack using bottom-up dynamic programming with tabulation, filling dp array iteratively.

Determine if there exists a subset of given set with sum equal to given sum.

Check if given set can be partitioned into two subsets such that sums of both subsets are equal.

Count number of subsets in a set which sum to a given sum.

Split set into two subsets such that difference of their sums is minimized.

Count the number of subset pairs whose difference of sums equals the given value.

Assign + or - signs to array elements such that the expression sums to target value. Count number of such ways.

Given weights and values of n items, and a knapsack capacity W, find the maximum value of items that can be put in the knapsack if an unlimited number of instances of each item can be used.

Given a rod of length n and prices for different lengths, determine the maximum revenue obtainable by cutting up the rod and selling the pieces. Unlimited pieces allowed.

Find the number of ways to make change for amount W using given coin denominations of infinite supply.

Given two sequences, find the length of their longest subsequence present in both of them using a recursive approach.

Use top-down dynamic programming (memoization) to efficiently find the length of longest common subsequence between two sequences.

Find length of longest common subsequence of two strings using iterative bottom-up dynamic programming.

Given two strings, find the length of the longest substring that is common to both.

Given two strings, print their longest common subsequence. If there are multiple, any one is acceptable.

Find the length of the shortest string that has both given strings as subsequences.

Find the minimum number of insertions and deletions to convert string 'a' to string 'b'.

Find the length of the longest subsequence of a given string that is also a palindrome.

Find the minimum number of characters to delete from a string to make it a palindrome.

Given two strings, print their shortest common supersequence.

Find the length of the longest subsequence that appears at least twice in the given string, where the two occurrences have different indices.

Check if a string 'a' is a subsequence of another string 'b'.

Given a sequence of matrix dimensions, determine the minimum number of scalar multiplications needed to multiply the entire chain using simple recursion.

Optimize the recursive MCM solution using top-down memoization to avoid redundant calculations.

Given a string, find the minimum number of cuts required to partition it into palindromic substrings using recursion.

Use memoization to optimize the palindrome partitioning recursive solution.

Compute minimum cuts for palindrome partitioning in O(n^2) time using precomputed palindrome table.

Count ways to parenthesize a boolean expression of T,F and operators &|^ so it evaluates to true, using recursion.

Optimize the recursive solution for expression evaluation by using a map to memoize subproblem results.

Use a 3D array dp[i][j][t] to memoize the count of ways for substring s[i..j] to evaluate to t (0/1).

Determine if one string is a scrambled form of another by recursive partition and swap.

Optimize the scramble string recursive solution by memoizing results for pairs of strings.

Find the minimum number of attempts needed in the worst case to determine the highest floor from which an egg can be dropped without breaking, using a purely recursive approach.

Use top-down memoization to optimize the recursive egg dropping solution, caching results for subproblems (E, F).

Optimize the memoized egg dropping solution by early stopping when minimum possible is reached.

Optimize the DP egg dropping solution by using binary search on the floor index to minimize attempts.

Find the length of the longest path between any two nodes in a binary tree. This path may or may not pass through the root.

Find the maximum path sum in a binary tree where the path can start and end at any node.

Find the maximum sum path between any two leaf nodes in a binary tree.