Welcome to Day 27 of my 100 Days of DSA challenge! Today, I focused on intermediate dynamic programming problems, diving into classic challenges like the longest increasing subsequence, longest common subsequence, and the 0/1 knapsack problem. By applying DP to problems such as coin change and target sum, I strengthened my problem-solving skills and deepened my understanding of this powerful technique.
Check out my GitHub repository for all the solutions and progress updates at: 100 Days of DSA
Let’s dive into the solutions! 🚀
1. Longest Increasing Subsequence Problem
This program calculates the length of the longest increasing subsequence (LIS) in a given array using dynamic programming. It maintains an array dp, where each element dp[i] stores the length of the longest increasing subsequence that ends at index i. The program iterates through each element and compares it with all previous elements to check if a subsequence can be extended. The final result is the maximum value in the dp array, which represents the length of the LIS.
Code:
#include <iostream>
#include <climits>
#include <cstring>
using namespace std;
#define MAX 1000 // Maximum size of the array
// Function to find the length of the longest increasing subsequence
int longest_increasing_subsequence(int arr[], int n) {
int dp[MAX]; // Array to store the length of LIS ending at each index
memset(dp, 0, sizeof(dp)); // Initialize dp array with 0
// Initialize the dp array where each element is at least an LIS of length 1
for (int i = 0; i < n; i++) {
dp[i] = 1;
}
// Fill the dp array using the LIS property
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[i] > arr[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
// Find the maximum value in dp, which represents the length of the longest increasing subsequence
int lis_length = 0;
for (int i = 0; i < n; i++) {
lis_length = max(lis_length, dp[i]);
}
return lis_length;
}
int main() {
int arr[] = {10, 22, 9, 33, 21, 50, 41, 60, 80};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Length of Longest Increasing Subsequence: " << longest_increasing_subsequence(arr, n) << endl;
return 0;
}
Output:
2. Longest Common Subsequence Problem
This program calculates the length of the longest common subsequence (LCS) between two given strings using dynamic programming. It creates a 2D array dp to store the lengths of LCS for substrings of the two input strings. The array is filled based on whether characters in the strings match, and the result for the full strings is stored in dp[m][n].
Code:
#include <iostream>
#include <cstring>
using namespace std;
#define MAX 1000 // Maximum size for the strings
// Function to find the length of the longest common subsequence
int longest_common_subsequence(char str1[], char str2[], int m, int n) {
int dp[MAX][MAX]; // 2D array to store the lengths of LCS
// Initialize the dp array with 0
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
dp[i][j] = 0;
}
}
// Fill the dp array
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (str1[i - 1] == str2[j - 1]) {
// If characters match, increment the length of LCS by 1
dp[i][j] = dp[i - 1][j - 1] + 1;
} else {
// Otherwise, take the maximum of the previous values
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
// The length of the longest common subsequence is stored in dp[m][n]
return dp[m][n];
}
int main() {
char str1[] = "ABCBDAB";
char str2[] = "BDCABB";
int m = strlen(str1);
int n = strlen(str2);
cout << "Length of Longest Common Subsequence: " << longest_common_subsequence(str1, str2, m, n) << endl;
return 0;
}
Output:
3. 0/1 Knapsack Problem
This program solves the 0/1 Knapsack Problem using dynamic programming. It creates a 2D table dp where each cell dp[i][w] represents the maximum value that can be achieved using the first i items with a knapsack capacity of w. It iteratively computes values by deciding whether to include or exclude each item based on its weight and value.
Code:
#include <iostream>
#include <cstring>
using namespace std;
#define MAX_ITEMS 100 // Maximum number of items
#define MAX_CAPACITY 1000 // Maximum capacity of the knapsack
// Function to solve the 0/1 Knapsack problem
int knapsack(int weights[], int values[], int num_items, int capacity) {
int dp[MAX_ITEMS + 1][MAX_CAPACITY + 1]; // 2D array to store the DP values
// Initialize the dp array
memset(dp, 0, sizeof(dp));
// Build the dp table
for (int i = 1; i <= num_items; i++) {
for (int w = 0; w <= capacity; w++) {
if (weights[i - 1] <= w) {
// Include the current item
dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
} else {
// Exclude the current item
dp[i][w] = dp[i - 1][w];
}
}
}
// The maximum value is stored in dp[num_items][capacity]
return dp[num_items][capacity];
}
int main() {
int weights[] = {1, 2, 3, 2};
int values[] = {10, 15, 40, 20};
int num_items = sizeof(weights) / sizeof(weights[0]);
int capacity = 5;
cout << "Maximum value in knapsack: " << knapsack(weights, values, num_items, capacity) << endl;
return 0;
}
Output:
4. Coin Change Problem
This program solves the Coin Change Problem using dynamic programming. It defines a dp array where dp[i] represents the minimum number of coins required to make the amount i. It initializes the array with a high value (INT_MAX) and sets dp[0] to 0. For each amount, it iterates through the coin denominations, updating the minimum number of coins required using a recurrence relation. The program outputs the minimum coins needed to make the given amount or indicates if it is not possible.
Code:
#include <iostream>
#include <climits>
#include <cstring>
using namespace std;
#define MAX_COINS 100 // Maximum number of coin denominations
#define MAX_AMOUNT 1000 // Maximum amount
// Function to find the minimum number of coins required to make a given amount
int coin_change(int coins[], int num_coins, int amount) {
int dp[MAX_AMOUNT + 1]; // Array to store the minimum coins for each amount
// Initialize the dp array
for (int i = 0; i <= amount; i++) {
dp[i] = INT_MAX; // Initialize all values as infinite
}
dp[0] = 0; // Base case: 0 coins are needed to make amount 0
// Fill the dp array
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < num_coins; j++) {
if (coins[j] <= i && dp[i - coins[j]] != INT_MAX) {
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
}
}
}
// If no combination can produce the amount, return -1
return dp[amount] == INT_MAX ? -1 : dp[amount];
}
int main() {
int coins[] = {1, 2, 5};
int num_coins = sizeof(coins) / sizeof(coins[0]);
int amount = 11;
int result = coin_change(coins, num_coins, amount);
if (result == -1) {
cout << "It is not possible to make the amount with the given coins." << endl;
} else {
cout << "Minimum coins required to make the amount: " << result << endl;
}
return 0;
}
Output:
5. Target Sum Problem
This program solves the Target Sum problem using dynamic programming. It uses a 2D dp table where dp[i][sum + offset] stores the number of ways to assign signs to the first i elements to reach the sum sum. An offset is used to handle negative sums. The table is filled iteratively by considering the two possible signs (+ and -) for each element in the array. The result is obtained from dp[n][target + offset].
Code:
#include <iostream>
#include <cstring>
using namespace std;
#define MAX_N 100 // Maximum number of elements in the array
#define MAX_SUM 2000 // Maximum possible absolute sum (positive + negative)
// Function to calculate the number of ways to assign signs to reach target sum
int target_sum(int arr[], int n, int target) {
int dp[MAX_N][MAX_SUM * 2 + 1]; // DP table with offset for negative indices
int offset = MAX_SUM; // Offset to handle negative indices
memset(dp, 0, sizeof(dp)); // Initialize dp table to 0
dp[0][offset] = 1; // Base case: one way to make sum 0 with no elements
// Fill the dp table
for (int i = 1; i <= n; i++) {
for (int sum = -MAX_SUM; sum <= MAX_SUM; sum++) {
if (dp[i - 1][sum + offset] > 0) {
dp[i][sum + arr[i - 1] + offset] += dp[i - 1][sum + offset];
dp[i][sum - arr[i - 1] + offset] += dp[i - 1][sum + offset];
}
}
}
// Return the number of ways to reach the target sum
return dp[n][target + offset];
}
int main() {
int arr[] = {1, 1, 1, 1, 1};
int n = sizeof(arr) / sizeof(arr[0]);
int target = 3;
int result = target_sum(arr, n, target);
cout << "Number of ways to reach the target sum: " << result << endl;
return 0;
}
Output:
Day 27 highlighted the effectiveness of dynamic programming in solving optimization and sequence-related problems. By mastering intermediate DP concepts like subsequences, knapsack, and coin change, I gained valuable insights into how to break down complex problems into manageable subproblems. These techniques are foundational for tackling more challenging DP problems in the future. 🚀