Introduction: Dynamic Programming | DSA in C++ - Software Development PDF Download

Introduction to Dynamic Programming in DSA C++

Dynamic Programming is a powerful algorithmic technique used to solve complex problems by breaking them down into simpler overlapping subproblems. It is widely used in computer science and plays a crucial role in various domains, including data structures and algorithms (DSA). In this article, we will explore the fundamentals of dynamic programming in C++ and understand how it can be applied to solve problems efficiently.

What is Dynamic Programming?

Dynamic Programming (DP) is an algorithmic paradigm that solves problems by breaking them down into smaller overlapping subproblems. It stores the solutions to these subproblems in a table or an array and reuses them whenever needed to avoid redundant computations. This technique greatly improves the efficiency of the overall solution.

The core idea behind dynamic programming is memoization or caching. It aims to solve each subproblem only once and store its solution for future reference. By avoiding duplicate calculations, the runtime of the algorithm is significantly reduced.

Key Concepts in Dynamic Programming

To effectively use dynamic programming, it is essential to understand the following key concepts:

• Optimal Substructure: A problem exhibits optimal substructure if its overall optimal solution can be constructed from optimal solutions of its subproblems. This property allows us to break down the problem into smaller subproblems and solve them independently.
• Overlapping Subproblems: In dynamic programming, subproblems can overlap, meaning the same subproblem is solved multiple times. By caching the solutions to these subproblems, we can avoid redundant computations and improve efficiency.

Steps to Solve a Dynamic Programming Problem

To solve a problem using dynamic programming, we can follow these general steps:

• Identify if the problem can be solved using dynamic programming: Look for the presence of optimal substructure and overlapping subproblems.
• Define the state: Determine the parameters that uniquely identify a subproblem.
• Formulate the recurrence relation: Express the solution to a larger problem in terms of the solutions to its smaller subproblems. This relation can be defined using a recursive equation or a mathematical formula.
• Design the dynamic programming algorithm:
  • Create a table or an array to store the solutions to subproblems.
  • Initialize the base cases or known solutions.
  • Use the recurrence relation to fill in the table or array bottom-up or top-down.
  • Retrieve the final solution from the table or array.

Analyze the time and space complexity: Assess the efficiency of the dynamic programming algorithm.

Examples with Code Explanation

Let's explore two classic examples to illustrate the concept of dynamic programming: Fibonacci Series and Longest Increasing Subsequence.

Fibonacci Series

The Fibonacci series is a sequence of numbers in which each number is the sum of the two preceding ones. Here's an implementation of the Fibonacci series using dynamic programming in C++:

#include <iostream>

using namespace std;

int fibonacci(int n) {

    int dp[n+1];

    dp[0] = 0;

    dp[1] = 1;

    for (int i = 2; i <= n; i++)

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

    return dp[n];

}

int main() {

    int n = 10;

    cout << "Fibonacci(" << n << ") = " << fibonacci(n) << endl;

    return 0;

}

Output:

Fibonacci(10) = 55

Explanation:

• We define an array 'dp' to store the Fibonacci values up to n.
• We initialize 'dp[0]' and 'dp[1]' as the base cases.
• Using a loop, we fill in the remaining values of 'dp' by summing the two preceding Fibonacci numbers.
• Finally, we return 'dp[n]' as the required Fibonacci number.

Longest Increasing Subsequence

The Longest Increasing Subsequence (LIS) problem involves finding the length of the longest subsequence of a given sequence in which the elements are in increasing order. Here's an implementation of LIS using dynamic programming in C++:

#include <iostream>

#include <vector>

using namespace std;

int lis(vector<int>& nums) {

    int n = nums.size();

    vector<int> dp(n, 1);

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

        for (int j = 0; j < i; j++) {

            if (nums[i] > nums[j] && dp[i] < dp[j] + 1)

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

        }

    }

    int maxLength = 0;

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

        if (dp[i] > maxLength)

            maxLength = dp[i];

    }

    return maxLength;

}

int main() {

    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};

    cout << "Length of Longest Increasing Subsequence: " << lis(nums) << endl;

    return 0;

}

Output:

Length of Longest Increasing Subsequence: 4

Explanation:

• We define a vector 'dp' to store the length of the longest increasing subsequence ending at each index.
• We initialize all elements of 'dp' to 1, as the minimum subsequence length is 1 (the element itself).
• Using nested loops, we compare each element with the preceding elements and update 'dp' accordingly.
• Finally, we find the maximum value in 'dp', which represents the length of the longest increasing subsequence.

Sample Problems with Solutions

Problem 1: Given a grid of size m x n, find the number of unique paths from the top-left corner to the bottom-right corner, moving only right or down.

Solution:

int uniquePaths(int m, int n) {

    vector<vector<int>> dp(m, vector<int>(n, 1));

    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];

        }

    }

    return dp[m-1][n-1];

}

Problem 2: Given an array of integers, find the maximum sum of a contiguous subarray.
Solution:

int maxSubarraySum(vector<int>& nums) {

    int n = nums.size();

    int maxSum = nums[0];

    int currSum = nums[0];

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

        currSum = max(nums[i], currSum + nums[i]);

        maxSum = max(maxSum, currSum);

    }

    return maxSum;

}

Conclusion

Dynamic Programming is a powerful technique that allows us to solve complex problems efficiently by breaking them down into simpler subproblems. By memoizing the solutions to these subproblems, we avoid redundant computations and improve the overall runtime of the algorithm. Understanding the key concepts and following the steps of dynamic programming enable us to apply this technique effectively. Through the examples and sample problems provided in this article, you have gained a foundational understanding of dynamic programming in C++.