Dynamic Programming

0/1 KNAPSACK :
1. Memoization

java cpp
2. Tabulation

cpp java
Subset sum equal to target :

1. Memoization:
2. Tabulation:
Equal Sum Partition Problem:
Difference Between Subset Sum and Equal Sum Partition

Subset Sum:

 Target sum is explicitly provided as input.

 Goal: Check if a subset exists that adds up to the target sum.

Equal Sum Partition:

 Derived target: The target sum is totalSum / 2, where totalSum is the sum of all
elements in the array.
 If totalSum is odd, it's immediately impossible to divide the array into two subsets
with equal sums. => return false
 Otherwise, it reduces to checking if a subset with the sum totalSum / 2 exists.
Key Differences

 Subset Sum: Directly checks for a given sum.

 Equal Sum Partition: Computes the target sum as totalSum / 2 and reduces the
problem to Subset Sum.

Code with Memoization

Count of Subsets Sum with a Given Sum
Difference From the Subset Sum Problem

Subset Sum Problem:

o Objective: Determine if there exists a subset with a sum equal to a given target
(true/false result).
o Approach: Binary decision-making (yes or no). OR operator is used to
determine this.

Count of Subsets Problem:

o Objective: Count the number of subsets whose sum equals the target.
o Approach: Extend the logic of the subset sum problem to count subsets instead
of merely deciding their existence. + operator is used to detrmine this.

Transition

 If the current element arr[i-1] is less than or equal to the target j:

t[i][j] = t[i−1][j] + t[i−1][j−arr[i−1]]

o t[i-1][j]: Count of subsets excluding the current element.
 o t[i-1][j - arr[i-1]]: Count of subsets including the current element.

 Otherwise: t[i][j]=t[i−1][j]

Code with Memoization:

Minimum_Subset_Sum_Difference
Count the Number of Subsets with a Given
Difference
(Count the Number of Partitions with a Given
Difference)
cpp:

java:
Target Sum
Rod Cutting Problem- Unbounded knapsack

Problem Summary
You are given a rod of length N, and a price array price[] where price[i] gives the
price of a rod of length i + 1.

Your goal is to cut the rod into smaller parts (or maybe not cut it at all) and
maximize the total price you get.

✂️ Example
Let:

N = 5;
price[] = {2, 5, 7, 8, 10};

This means:

Length 1 → ₹2

Length 2 → ₹5

Length 3 → ₹7

Length 4 → ₹8
 Length 5 → ₹1

You can cut the rod into any combination of lengths — e.g., 2+3, 1+1+1+2, 5 — to
maximize profit.

Connection to Unbounded Knapsack

This is exactly like Unbounded Knapsack, because:

You can use any piece length multiple times (e.g., length-1 rod can be used 5 times
if needed)

You want the maximum value for a given total rod length N

Understanding i and len

Variable Role
i Current piece length index we're considering (1 to N)
len Current target rod length we are trying to build (1 to N)

DP Table Meaning

We define a 2D table:

dp[i][len] = maximum price we can get using the first i piece lengths
(1 to i) to build a rod of length `len`.

Example Build

We iterate:

for (int i = 1; i <= n; i++) {

for (int len = 1; len <= n; len++) {

Now, for each dp[i][len]:

1. If we can take this length i (i.e., i <= len):

dp[i][len] = max(
dp[i - 1][len], // don’t cut at length i (skip
it)
 price[i - 1] + dp[i][len - i] // cut at length i, stay on i
(UNBOUNDED)
);

Why dp[i][len - i]?

� You cut a rod of size i, now you are left with a rod of size len - i
Since it's unbounded, you can use the same length again, so you stay at i.

2. If we cannot take this length (i.e., i > len):

dp[i][len] = dp[i - 1][len]; // Just skip using this length

✅ Full Code with Comments

#include <iostream>
#include <vector>
using namespace std;

int cutRod(vector<int>& price, int n) {

vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

// Build the table bottom-up

for (int i = 1; i <= n; i++) { // piece lengths from 1 to n
for (int len = 1; len <= n; len++) {// rod lengths from 1to n
if (i <= len) {
dp[i][len] = max(
dp[i - 1][len],// skip this piece length
price[i - 1] + dp[i][len - i] // take this piece
);
} else {
dp[i][len] = dp[i - 1][len]; // can't take this piece
}
}
}

return dp[n][n]; // max value using all piece lengths to build

rod of size n
}

int main() {
vector<int> price = {2, 5, 7, 8, 10};
int n = [Link]();
cout << "Maximum profit: " << cutRod(price, n) << endl;
return 0;
}
Coin change problem: Maximum number of
ways

Problem Statement

Given an integer array coins[] representing different coin denominations and a

target amount sum, find the total number of ways to make the sum using the available
coins. You can use any coin any number of times.

✅ Example

coins[] = {1, 2, 3}, sum = 4

Possible combinations:

1+1+1+1
1+1+2
2+2
1+3

Total ways = 4
Bottom up :
Dry Run Help

We build answers like:

4 = 1+1+1+1

4 = 1+1+2

4 = 2+2

4 = 1+3

It uses the same coin multiple times (unbounded).

Coin change problem: Minimum

number of coins
Longest Common Subsequence
Longest Common Substring
Printing Longest common
subsequence
Shortest Common SuperSequence

m+n-lcs=length of superSequence

Length of SCS=Length of s1+Length of s2−Length of LCS

Minimum Number of Insertion and
Deletion to convert String a to
String b
Longest Palindromic Subsequence
Minimum number of deletion in a
string to make it a palindrome
Longest repeating subsequence

The problem is similar to the Longest Common Subsequence (LCS), but

with an important constraint:

1. The two subsequences must come from the same string.

2. Their indices in the original string must be different (i.e., i≠ji \neq ji =j).
Sequence Pattern Matching

Problem Statement

Given two strings s1s1s1 and s2s2s2, determine if s1s1s1 is a subsequence of s2s2s2.
A subsequence allows characters to be non-contiguous, but their order must remain
the same.

For example:

 s1="abc"s1 = "abc"s1="abc", s2="ahbgdc"s2 = "ahbgdc"s2="ahbgdc": s1s1s1 is a

subsequence of s2s2s2.
 s1="axc"s1 = "axc"s1="axc", s2="ahbgdc"s2 = "ahbgdc"s2="ahbgdc": s1s1s1 is
not a subsequence of s2s2s2.

Approach

This can be solved using the Longest Common Subsequence (LCS) concept.

1. Compute the LCS of s1s1s1 and s2s2s2.

2. If the LCS length is equal to the length of s1s1s1, then s1s1s1 is a subsequence of
s2s2s2.
Minimum number of
insertion/deletion in a string to
make it a palindrome

Key Insight:

The minimum number of insertions required is equal to the difference between the
length of the string and the length of its Longest Palindromic Subsequence (LPS).

 LPS of a string is the longest subsequence (not necessarily contiguous) of the string
that is a palindrome.
 The reason why this works is because the characters that are part of the LPS already
form a palindrome, so the characters that are not part of the LPS will need to be
inserted to make the string a palindrome.

Steps to Solve the Problem:

Step 1: Find the Longest Palindromic Subsequence (LPS) of the string.

1. LPS of a string can be calculated by finding the Longest Common

Subsequence (LCS) between the string and its reverse.

Step 2: Subtract the length of LPS from the length of the string to get the
minimum number of insertions required.

2. Minimum Insertions=[Link]() - LPS(s)

Approach:

1. Reverse the given string to get a new string.

2. Find the LCS of the original string and its reverse.
3. The result will be: Minimum Insertions=[Link]() - LPS(s)
Assign Cookies
Example 1:
Input: g = [1,2,3], s = [1,1]Output: 1Explanation: You have 3 children and 2 cookies. The
greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child
whose greed factor is 1 content.
You need to output 1.

Example 2:
Input: g = [1,2], s = [1,2,3]Output: 2Explanation: You have 2 children and 3 cookies. The
greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int findContentChildren(vector<int>& g, vector<int>& s) {

sort([Link](), [Link]()); // Sort greed factors
sort([Link](), [Link]()); // Sort cookie sizes

int child = 0, cookie = 0;

while (child < [Link]() && cookie < [Link]()) {
if (s[cookie] >= g[child]) {
// Assign cookie to child
child++;
}
cookie++;
}
return child; // Total content children
}

int main() {
vector<int> g = {1, 2}; // Children greed
vector<int> s = {1, 2, 3}; // Cookie sizes

cout << "Max content children: " << findContentChildren(g, s) << endl;
return 0;
}
Distinct Subsequences Problem

✅ What is dp[i][j]?

It means:

How many ways can I make the first j letters of t from the first i letters of s?

�� When the letters match:

If s[i-1] == t[j-1], we have two choices:

✅ Use the matching letter

❌ Or skip it and try the next letter in s

So we add both choices:

dp[i][j] = dp[i-1][j-1] + dp[i-1][j];

When the letters don't match:

We can only skip:

dp[i][j] = dp[i-1][j];
 Deletion

I
n
s
e
r
t
i
o
n

0 1 1 mei se min nikalo and just add 1 to it because humei min operation karne h