Welcome to Day 28 of my 100 Days of DSA challenge! Today, I delved into advanced dynamic programming problems, tackling challenges like partitioning a set into equal sums, calculating edit distances, and finding unique paths in a grid. These problems pushed my understanding of DP to new heights, focusing on more complex problem-solving techniques.
Check out my GitHub repository for all the solutions and progress updates at: 100 Days of DSA
Let's dive into the solutions! 🚀
1. Partition Equal Subset Sum
This program solves the "Partition Equal Subset Sum" problem using dynamic programming. It first calculates the total sum of the array. If the sum is odd, partitioning into two equal subsets is impossible. Otherwise, it attempts to find if there is a subset with sum equal to half of the total sum using a dynamic programming approach. A dp array is used, where dp[i] indicates whether a subset sum i can be formed. If dp[target] is true (where target is half of the sum), the array can be partitioned; otherwise, it cannot.
Code:
#include <iostream>
#include <climits>
#include <cstring>
using namespace std;
#define MAX 1000 // Maximum sum for the subset
// Function to check if it's possible to partition the array into two subsets with equal sum
bool can_partition(int arr[], int n) {
int sum = 0;
// Calculate the total sum of the elements in the array
for (int i = 0; i < n; i++) {
sum += arr[i];
}
// If the total sum is odd, partition is not possible
if (sum % 2 != 0) {
return false;
}
int target = sum / 2; // The target sum for one subset
// dp[i] will be true if a subset with sum i can be formed
bool dp[target + 1];
memset(dp, false, sizeof(dp)); // Initialize all dp values to false
dp[0] = true; // Base case: a sum of 0 is always possible (empty subset)
// Fill the dp array
for (int i = 0; i < n; i++) {
for (int j = target; j >= arr[i]; j--) {
if (dp[j - arr[i]]) {
dp[j] = true;
}
}
}
// The answer will be stored in dp[target], if it's true
return dp[target];
}
int main() {
int arr[] = {1, 5, 11, 5};
int n = sizeof(arr) / sizeof(arr[0]);
if (can_partition(arr, n)) {
cout << "The array can be partitioned into two subsets with equal sum." << endl;
} else {
cout << "The array cannot be partitioned into two subsets with equal sum." << endl;
}
return 0;
}
Output:
2. Edit Distance Problem
This program computes the edit distance (minimum number of operations) required to convert one string (str1) into another (str2). It uses dynamic programming to fill a 2D table dp where dp[i][j] represents the edit distance between the first i characters of str1 and the first j characters of str2. The three possible operations (insert, delete, and replace) are considered at each step, and the minimum of these values is stored in the table. The final value dp[m][n] gives the minimum number of operations required to convert str1 into str2.
Code:
#include <iostream>
#include <cstring>
using namespace std;
#define MAX 1000 // Maximum size for the strings
// Function to find the minimum number of operations required to convert str1 to str2
int edit_distance(char str1[], char str2[], int m, int n) {
int dp[MAX][MAX]; // 2D array to store the edit distance
// Fill the dp array
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0) {
dp[i][j] = j; // If str1 is empty, all characters of str2 need to be inserted
} else if (j == 0) {
dp[i][j] = i; // If str2 is empty, all characters of str1 need to be deleted
} else if (str1[i - 1] == str2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1]; // No operation needed if characters match
} else {
dp[i][j] = 1 + min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1]));
// Min operation among replace, delete, and insert
}
}
}
// The result is the edit distance to convert str1 to str2
return dp[m][n];
}
int main() {
char str1[MAX], str2[MAX];
cout << "Enter the first string: ";
cin >> str1;
cout << "Enter the second string: ";
cin >> str2;
int m = strlen(str1);
int n = strlen(str2);
cout << "Edit Distance: " << edit_distance(str1, str2, m, n) << endl;
return 0;
}
Output:
3. Unique Paths Problem
This program calculates the number of unique paths in an m x n grid using dynamic programming. It initializes the first row and column of a 2D array to 1, as there's only one way to reach cells in these edges. The remaining cells' values are calculated as the sum of paths from the cell above and the cell to the left. The result is stored in the bottom-right corner of the grid.
Code:
#include <iostream>
using namespace std;
#define MAX 100
// Function to calculate the number of unique paths in a grid
int unique_paths(int m, int n) {
int dp[MAX][MAX]; // 2D array to store the number of paths to each cell
// Initialize the first row and first column to 1 (only one way to reach these cells)
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int j = 0; j < n; j++) {
dp[0][j] = 1;
}
// Fill the dp array
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; // Sum of paths from top and left
}
}
return dp[m - 1][n - 1]; // Return the total number of paths to the bottom-right corner
}
int main() {
int m, n;
cout << "Enter the number of rows: ";
cin >> m;
cout << "Enter the number of columns: ";
cin >> n;
cout << "Number of unique paths: " << unique_paths(m, n) << endl;
return 0;
}
Output:
4. Palindromic Subsequences
This program calculates the length of the longest palindromic subsequence in a given string. It uses a 2D array dp to store results for substrings. Substrings of length 1 are initialized to 1. For longer substrings, it checks if the first and last characters match; if they do, the length is increased by 2 plus the result for the inner substring. Otherwise, the maximum value from excluding either the first or last character is taken. The result for the full string is stored in dp[0][n-1].
Code:
#include <iostream>
#include <cstring>
using namespace std;
#define MAX 1000
// Function to calculate the length of the longest palindromic subsequence
int longest_palindromic_subsequence(char str[], int n) {
int dp[MAX][MAX]; // 2D array to store lengths of palindromic subsequences
// Base case: A single character is always a palindrome of length 1
for (int i = 0; i < n; i++) {
dp[i][i] = 1;
}
// Fill the dp array for substrings of length 2 and more
for (int length = 2; length <= n; length++) {
for (int i = 0; i <= n - length; i++) {
int j = i + length - 1; // Ending index of substring
if (str[i] == str[j]) {
dp[i][j] = dp[i + 1][j - 1] + 2; // Characters match
} else {
dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]); // Max of excluding either character
}
}
}
return dp[0][n - 1]; // Length of longest palindromic subsequence for the full string
}
int main() {
char str[MAX];
cout << "Enter the string: ";
cin >> str;
int n = strlen(str);
cout << "Length of Longest Palindromic Subsequence: " << longest_palindromic_subsequence(str, n) << endl;
return 0;
}
Output:
5. Rod Cutting Problem
This program calculates the maximum profit from cutting a rod of a given length using dynamic programming. A 2D array dp is used to store the maximum profit for each subproblem. For each length, it decides whether to include or exclude the current cut, based on which gives higher profit. The result for the full rod is stored in dp[n][rod_length].
Code:
#include <iostream>
#include <cstring>
using namespace std;
#define MAX 1000
// Function to find the maximum profit from cutting the rod
int rod_cutting(int length[], int price[], int n, int rod_length) {
int dp[MAX][MAX]; // 2D array to store maximum profit
// Initialize the dp array
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= rod_length; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0; // Base case: No rod or no length to cut
} else if (length[i - 1] <= j) {
// Max profit by including or excluding the current length
dp[i][j] = max(price[i - 1] + dp[i][j - length[i - 1]], dp[i - 1][j]);
} else {
// Exclude the current length
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][rod_length]; // Maximum profit
}
int main() {
int length[] = {1, 2, 3, 4, 5}; // Possible lengths
int price[] = {2, 5, 7, 8, 10}; // Corresponding prices
int rod_length = 5; // Length of the rod
int n = sizeof(length) / sizeof(length[0]);
cout << "Maximum Profit: " << rod_cutting(length, price, n, rod_length) << endl;
return 0;
}
Output:
Day 28 showcased the depth and versatility of advanced dynamic programming techniques, tackling problems like partitioning subsets, calculating edit distances, and optimizing grid traversals. These challenges reinforced the importance of structuring solutions efficiently and laid a strong foundation for approaching even more complex problems. 🚀