Back to Course

0% Complete
0/0 Steps

Lesson 44 of 48
In Progress

# Dynamic Programming in C++

Dynamic programming is a powerful optimization technique used in computer science and engineering. It is an approach to solving complex problems by breaking them down into smaller, simpler subproblems and then combining the solutions of those subproblems to obtain the optimal solution for the original problem. As a result, dynamic programming is widely used in computer science and engineering to solve a variety of problems, from scheduling tasks to finding the shortest path between two points.

The purpose of this article is to introduce the concept of dynamic programming and provide an overview of its applications in C++. We will discuss the fundamentals of dynamic programming and the various techniques used to solve dynamic programming problems. We will also provide examples of dynamic programming algorithms written in C++ and demonstrate how they can be used to solve complex problems. Finally, we will provide five coding exercises with solutions to test the reader’s understanding of the material covered in this article.

## What is Dynamic Programming?

Dynamic programming is an optimization technique used to solve complex problems by breaking them down into smaller, simpler subproblems. The idea behind dynamic programming is that if we can find the optimal solution to each subproblem, then we can combine the solutions of all the subproblems to obtain the optimal solution for the original problem.

Dynamic programming is a bottom-up approach to problem solving, which means that it starts with the smallest subproblems and works its way up to the larger problem. This is in contrast to a top-down approach, where we start with the larger problem and break it down into smaller subproblems.

Dynamic programming is typically used to solve optimization problems, such as the shortest path problem or the knapsack problem. It can also be used to solve problems that involve making decisions, such as scheduling tasks or selecting the best investment portfolio.

## Dynamic Programming in C++

Dynamic programming can be implemented in any programming language, but it is particularly well-suited for C++ due to its powerful features, such as templates and operator overloading.

To illustrate how dynamic programming can be implemented in C++, let’s consider the following example:

Given a set of numbers, we want to find the maximum sum of any subset of those numbers.

To solve this problem, we can use the following dynamic programming algorithm written in C++:

#include <iostream>
#include <vector>

using namespace std;

// Function to find the maximum sum of any subset of the given set of numbers
int maxSubsetSum(vector<int> numbers) {
// Create a 2D array to store the results of the subproblems
int dp[numbers.size()+1][numbers.size()+1];

// Initialize the array with 0
for (int i = 0; i <= numbers.size(); i++) {
for (int j = 0; j <= numbers.size(); j++) {
dp[i][j] = 0;
}
}

// Solve the subproblems
for (int i = 1; i <= numbers.size(); i++) {
for (int j = 1; j <= numbers.size(); j++) {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + numbers[i-1]);
}
}

// Return the maximum sum
return dp[numbers.size()][numbers.size()];
}

int main() {
vector<int> numbers = {1, 2, 3, 4, 5};
cout << "Maximum sum = " << maxSubsetSum(numbers) << endl;
return 0;
}

In this example, we have used the dynamic programming approach to solve the maximum subset sum problem. The algorithm uses a 2D array to store the results of the subproblems and then finds the maximum sum by iterating over the array and calculating the maximum sum for each subproblem.

Dynamic programming can be used to solve a variety of problems, such as the 0-1 knapsack problem, the shortest path problem, and the maximum sum subarray problem. In each of these problems, we can use dynamic programming to find the optimal solution.

## Conclusion

In this article, we discussed the concept of dynamic programming and how it can be used to solve complex problems. We discussed the fundamentals of dynamic programming and provided examples of dynamic programming algorithms written in C++. We also discussed how dynamic programming can be used to solve optimization problems, such as the 0-1 knapsack problem, the shortest path problem, and the maximum sum subarray problem.

## Exercises

#### Given an array of integers, find the maximum sum of any contiguous subarray.

#include <iostream>
#include <vector>

using namespace std;

// Function to find the maximum sum of any contiguous subarray
int maxSubarraySum(vector<int> numbers) {
// Create a 1D array to store the results of the subproblems
int dp[numbers.size()+1];

// Initialize the array with 0
for (int i = 0; i <= numbers.size(); i++) {
dp[i] = 0;
}

// Solve the subproblems
for (int i = 1; i <= numbers.size(); i++) {
dp[i] = max(dp[i-1], dp[i-1] + numbers[i-1]);
}

// Return the maximum sum
return dp[numbers.size()];
}

int main() {
vector<int> numbers = {1, 2, 3, 4, 5};
cout << "Maximum sum = " << maxSubarraySum(numbers) << endl;
return 0;
}

#### Given a set of items with values and weights, find the maximum value you can obtain by selecting a subset of the items such that the total weight does not exceed a given weight limit.

#include <iostream>
#include <vector>

using namespace std;

// Function to find the maximum value obtainable from a subset of items with given weights and values
int knapsack(vector<int> values, vector<int> weights, int weightLimit) {
// Create a 2D array to store the results of the subproblems
int dp[values.size()+1][weightLimit+1];

// Initialize the array with 0
for (int i = 0; i <= values.size(); i++) {
for (int j = 0; j <= weightLimit; j++) {
dp[i][j] = 0;
}
}

// Solve the subproblems
for (int i = 1; i <= values.size(); i++) {
for (int j = 1; j <= weightLimit; j++) {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1]);
}
}

// Return the maximum value
return dp[values.size()][weightLimit];
}

int main() {
vector<int> values = {1, 2, 3, 4, 5};
vector<int> weights = {1, 2, 3, 4, 5};
int weightLimit = 10;
cout << "Maximum value = " << knapsack(values, weights, weightLimit) << endl;
return 0;
}

#### Given a matrix of positive integers and a starting coordinates, find the longest path from the starting coordinates such that all the elements in the path are in increasing order.

#include <iostream>
#include <vector>

using namespace std;

// Function to find the longest path from a given starting coordinates such that all the elements in the path are in increasing order
int longestPath(vector<vector<int>> matrix, int row, int col) {
// Create a 2D array to store the results of the subproblems
int dp[row+1][col+1];

// Initialize the array with 0
for (int i = 0; i <= row; i++) {
for (int j = 0; j <= col; j++) {
dp[i][j] = 0;
}
}

// Solve the subproblems
for (int i = 1; i <= row; i++) {
for (int j = 1; j <= col; j++) {
// Check if the current element is greater than the one to the left
if (matrix[i][j] > matrix[i][j-1]) {
dp[i][j] = max(dp[i][j], dp[i][j-1] + 1);
}

// Check if the current element is greater than the one to the top
if (matrix[i][j] > matrix[i-1][j]) {
dp[i][j] = max(dp[i][j], dp[i-1][j] + 1);
}
}
}

// Return the longest path
return dp[row][col];
}

int main() {
vector<vector<int>> matrix = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
};
int row = 2;
int col = 2;
cout << "Longest path = " << longestPath(matrix, row, col) << endl;
return 0;
}

#### Given a set of tasks with start times and end times, find the maximum number of tasks that can be completed in a given time frame.

#include <iostream>
#include <vector>

using namespace std;

// Function to find the maximum number of tasks that can be completed in a given time frame
// Create a 1D array to store the results of the subproblems
int dp[timeFrame+1];

// Initialize the array with 0
for (int i = 0; i <= timeFrame; i++) {
dp[i] = 0;
}

// Solve the subproblems
for (int i = 1; i <= timeFrame; i++) {
for (int j = 0; j < tasks.size(); j++) {
// Check if the current task can be completed in the given time frame
dp[i] = max(dp[i], dp[i - tasks[j].second] + 1);
}
}
}

// Return the maximum number of tasks
return dp[timeFrame];
}

int main() {
vector<pair<int, int>> tasks = {{2, 3}, {2, 4}, {3, 5}, {4, 5}};
int timeFrame = 5;
return 0;
}

#### Given a set of coins and a total amount, find the minimum number of coins required to make the total amount.

#include <iostream>
#include <vector>

using namespace std;

// Function to find the minimum number of coins required to make the given total amount
int minCoins(vector<int> coins, int amount) {
// Create a 1D array to store the results of the subproblems
int dp[amount+1];

// Initialize the array with amount+1
for (int i = 0; i <= amount; i++) {
dp[i] = amount+1;
}

// Solve the subproblems
dp = 0;
for (int i = 1; i <= amount; i++) {
for (int j = 0; j < coins.size(); j++) {
// Check if the current coin is less than or equal to the amount
if (coins[j] <= i) {
dp[i] = min(dp[i], dp[i - coins[j]] + 1);
}
}
}

// Return the minimum number of coins
return dp[amount];
}

int main() {
vector<int> coins = {1, 2, 5};
int amount = 11;
cout << "Minimum number of coins = " << minCoins(coins, amount) << endl;
return 0;
}