Coding Interview Questions Interview Questions and Answers

New 70 Dynamic Programming Question

Deepak Vishwakarma July 29, 2023Last Updated: July 29, 2023

0 1 55 minutes read

Table of Contents

Introduction

Dynamic Programming is a problem-solving technique widely used in computer science and interviews. It breaks down complex problems into simpler subproblems, solving each subproblem only once and storing the results for future reference. This approach optimizes time and space efficiency, making it a valuable tool. Dynamic Programming problems often involve finding the optimal solution or calculating the maximum or minimum value of a function. Common examples include the Fibonacci sequence, knapsack problems, and finding the longest common subsequence. By understanding the principles and strategies of Dynamic Programming, you can tackle these challenging interview questions effectively and impress your interviewer.

Questions

1. What is Dynamic Programming (DP)?

Dynamic Programming (DP) is a technique used in computer programming to solve problems by breaking them down into smaller overlapping subproblems and solving each subproblem only once. DP stores the solutions to subproblems in a table (usually an array) to avoid redundant computations, making it more efficient than naive recursion.

Example – Fibonacci Series:
The classic example to illustrate DP is the Fibonacci series calculation using recursion:

C++

#include <iostream>
#include <vector>

int fibonacciRecursive(int n) {
    if (n <= 1)
        return n;
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

int main() {
    int n = 10;
    std::cout << "Fibonacci(" << n << ") using recursion: " << fibonacciRecursive(n) << std::endl;
    return 0;
}

In this example, the recursive function fibonacciRecursive calculates the nth Fibonacci number. However, this naive recursive approach leads to a lot of redundant calculations, making it inefficient for larger values of n.

2. How is dynamic programming different from recursion and divide-and-conquer?

Aspect	Recursion	Divide and Conquer	Dynamic Programming
Approach	Top-down	Top-down	Both top-down and bottom-up
Subproblems	Overlapping subproblems	Independent subproblems	Overlapping subproblems
Repeated computations	Common (inefficient)	Avoided (efficient)	Avoided (efficient)
Storage	No intermediate storage	No intermediate storage	Table for storing subproblem results
Examples	Fibonacci, Factorial	Binary Search, Merge Sort	Fibonacci, Knapsack, LCS, Grid paths

3. What are the key features of a problem that make it suitable for using DP in its solution?

To be suitable for a DP solution, a problem must exhibit the following key features:

Overlapping Subproblems: The problem can be broken down into smaller subproblems, and the same subproblems are encountered multiple times during the solution.
Optimal Substructure: The optimal solution to the problem can be constructed from optimal solutions to its subproblems.

Example – Knapsack Problem
The Knapsack problem is a classic example of a problem suitable for DP. It involves selecting items to maximize the total value in a knapsack with a limited weight capacity.

4. What are the steps to solve a DP problem?

The general steps to solve a DP problem are as follows:

Identify the recurrence relation (the relationship between the problem and its subproblems).
Decide whether to use a top-down (memoization) or bottom-up (tabulation) approach.
Create a table (array) to store subproblem results.
Initialize the base cases of the problem (the smallest subproblems).
Fill up the table using the recurrence relation to solve larger subproblems.
Return the solution to the original problem from the table.

Example – Fibonacci Series using Bottom-up (Tabulation):

C++

#include <iostream>
#include <vector>

int fibonacciDP(int n) {
    std::vector<int> dp(n + 1, 0);

    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;
    std::cout << "Fibonacci(" << n << ") using DP (tabulation): " << fibonacciDP(n) << std::endl;
    return 0;
}

5. What are the main elements of a Dynamic Programming problem?

The main elements of a Dynamic Programming problem include:

Table (Array): A data structure used to store solutions to subproblems. The table is often indexed to represent the parameters of the problem.
Base Cases: The smallest subproblems that can be directly solved.
Recurrence Relation: The relationship between the problem and its subproblems. It defines how the solutions of subproblems can be used to solve the original problem.

Example – Computing Factorials using DP:

C++

#include <iostream>
#include <vector>

int factorialDP(int n) {
    std::vector<int> dp(n + 1, 0);

    dp[0] = 1;

    for (int i = 1; i <= n; ++i) {
        dp[i] = i * dp[i - 1];
    }

    return dp[n];
}

int main() {
    int n = 5;
    std::cout << "Factorial of " << n << " using DP: " << factorialDP(n) << std::endl;
    return 0;
}

6. What is the concept of overlapping subproblems in Dynamic Programming?

Overlapping subproblems occur when the same subproblems are solved multiple times in the process of solving the original problem. These redundant calculations lead to inefficiency, especially in recursive algorithms. Dynamic Programming avoids this inefficiency by storing the results of subproblems in a table (array) and using them directly when needed.

Example – Fibonacci Series using Top-down (Memoization):

C++

#include <iostream>
#include <vector>

std::vector<int> dp(100, -1);

int fibonacciMemoization(int n) {
    if (n <= 1)
        return n;

    if (dp[n] != -1)
        return dp[n];

    dp[n] = fibonacciMemoization(n - 1) + fibonacciMemoization(n - 2);
    return dp[n];
}

int main() {
    int n = 10;
    std::cout << "Fibonacci(" << n << ") using DP (memoization): " << fibonacciMemoization(n) << std::endl;
    return 0;
}

In this example, the dp array is used to store the results of subproblems, and before calculating a Fibonacci number, we check if it has already been computed to avoid redundant calculations.

7. Explain the concept of optimal substructure in DP. Explain with examples and code

Optimal substructure is a key concept in dynamic programming (DP). It means that the optimal solution to a larger problem can be constructed by combining optimal solutions to its smaller subproblems. If a problem exhibits optimal substructure, it allows us to break down the problem into smaller overlapping subproblems, solve them independently, and then combine their solutions to find the overall optimal solution.

Longest Increasing Subsequence (LIS) Problem:
Given an array of integers, find the length of the longest increasing subsequence.

Example:
Given the array [10, 22, 9, 33, 21, 50, 41, 60, 80], the longest increasing subsequence is [10, 22, 33, 50, 60, 80] with a length of 6.

Now, let’s see how optimal substructure is demonstrated in this problem.

Optimal Substructure in LIS Problem:
Suppose we have found the longest increasing subsequence (LIS) of a prefix of the array ending at some index i. Let’s call this LIS as LIS(i). If we know the LIS ending at index i, we can use it to extend the LIS for the entire array up to index i+1.

To find LIS(i+1), we iterate over the elements from index 0 to i and check if the element at index i+1 is greater than the element at index j. If it is, we can extend the LIS ending at index j by adding the element at index i+1 to it.

Here’s the C++ code to find the length of the longest increasing subsequence:

C++

#include <iostream>
#include <vector>

int lisLength(const std::vector<int>& nums) {
    int n = nums.size();
    std::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] = std::max(dp[i], dp[j] + 1);
            }
        }
    }

    int maxLength = 0;
    for (int length : dp) {
        maxLength = std::max(maxLength, length);
    }

    return maxLength;
}

int main() {
    std::vector<int> nums = {10, 22, 9, 33, 21, 50, 41, 60, 80};
    std::cout << "Length of the longest increasing subsequence: " << lisLength(nums) << std::endl;
    return 0;
}

In this code, the dp array is used to store the length of the longest increasing subsequence ending at each index. We calculate this value using optimal substructure: If an element at index i is greater than any element at previous indices j, we can extend the LIS ending at index j and obtain LIS(i).

The time complexity of this solution is O(n^2) since we have two nested loops. However, this problem can also be solved more efficiently using the Patience Sorting algorithm with a time complexity of O(n log n).

8. What is the difference between top-down (memoization) and bottom-up (tabulation) approaches in DP?

Aspect	Top-Down (Memoization)	Bottom-Up (Tabulation)
Approach	Recursion-based	Iteration-based
Storage	Additional stack space	Table (array)
Order of Calculation	Solve from larger to smaller	Solve from smaller to larger
Examples	Fibonacci, LCS	Fibonacci, LCS

9. What is ‘state’ in DP?

In dynamic programming (DP), a ‘state’ refers to a unique configuration of parameters that defines a subproblem within the larger problem. It represents a specific situation that needs to be solved as part of the overall problem.

In the context of DP, breaking down a complex problem into smaller overlapping subproblems is a key strategy to efficiently find the optimal solution. Each subproblem is identified by its state, which is usually represented by one or more variables or indices. By storing the solutions to subproblems in a table (usually an array), DP avoids redundant calculations and allows for more efficient problem-solving.

Example: Longest Common Subsequence (LCS) Problem:

In the LCS problem, given two sequences, the task is to find the longest subsequence that is common to both sequences. The state in this problem can be represented by two variables, i and j, which denote the indices of the elements being compared in the two sequences.

Let’s say we have two sequences: “ABCDGH” and “AEDFHR”. The state (i, j) represents the subproblem of finding the LCS of the prefixes of the sequences up to the ith and jth positions, respectively.

The DP table will be filled using this state (i, j), and the optimal solution to the LCS problem will be derived from the solutions to smaller subproblems with different combinations of i and j.

The LCS problem’s state space will be a 2D array, where each entry in the table represents the LCS of a specific state (i, j) in the sequences.

By breaking down the problem into smaller overlapping subproblems, the DP algorithm efficiently computes the LCS for different states and eventually provides the optimal solution for the entire problem.

10. What is the time and space complexity of a dynamic programming algorithm?

The time and space complexity of a dynamic programming algorithm depends on whether it uses a top-down (memoization) or bottom-up (tabulation) approach.

Time Complexity: For both approaches, the time complexity is determined by the number of unique subproblems to be solved. In general, it is represented by O(N), where N is the size of the input.
Space Complexity: For top-down (memoization), the space complexity is determined by the size of the table (array) used to store the results of subproblems. In the worst case, it can be O(N). For bottom-up (tabulation), the space complexity is also determined by the size of the table, which is O(N) in most cases.

11. What do you understand by ‘memoization’ in dynamic programming?

Memoization in dynamic programming is an optimization technique that involves storing the results of expensive function calls and returning the cached result when the same inputs occur again. In other words, it avoids redundant calculations by remembering previously computed solutions and reusing them instead of recalculating.

Example: Fibonacci Series using Memoization:

C++

#include <iostream>
#include <vector>

std::vector<int> dp(100, -1);

int fibonacciMemoization(int n) {
    if (n <= 1)
        return n;

    if (dp[n] != -1)
        return dp[n];

    dp[n] = fibonacciMemoization(n - 1) + fibonacciMemoization(n - 2);
    return dp[n];
}

int main() {
    int n = 10;
    std::cout << "Fibonacci(" << n << ") using DP (memoization): " << fibonacciMemoization(n) << std::endl;
    return 0;
}

In this code, the dp array is used to store the results of subproblems in the Fibonacci series. Before calculating the nth Fibonacci number, the algorithm checks if it has already been computed (memoized) in the dp array. If so, it directly returns the cached result, avoiding redundant calculations. This significantly improves the efficiency of the Fibonacci series calculation.

12. Can you explain how DP is used in the Longest Common Subsequence problem?

Dynamic Programming (DP) is commonly used to solve the Longest Common Subsequence (LCS) problem efficiently. The LCS problem involves finding the longest subsequence that is common to two given sequences. A subsequence is a sequence that can be derived from another sequence by deleting zero or more elements without changing the order of the remaining elements.

C++ Code for LCS Problem (Bottom-up approach – Tabulation):

C++

#include <iostream>
#include <vector>

int longestCommonSubsequence(const std::string& text1, const std::string& text2) {
    int m = text1.length();
    int n = text2.length();

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

    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[m][n];
}

int main() {
    std::string text1 = "ABCDGH";
    std::string text2 = "AEDFHR";
    std::cout << "Length of Longest Common Subsequence: " << longestCommonSubsequence(text1, text2) << std::endl;
    return 0;
}

In this code, the dp table is used to store the lengths of the longest common subsequences between substrings of text1 and text2. The LCS is obtained by tracing back the path from the bottom-right corner of the table to the top-left corner. The time complexity of this solution is O(m * n), where m and n are the lengths of text1 and text2, respectively.

13. Can you explain how DP is used in the Knapsack problem?

Dynamic Programming (DP) is commonly used to solve the Knapsack problem efficiently. The Knapsack problem is a classic optimization problem where given a set of items, each with a weight and a value, we need to determine the maximum value we can obtain by selecting a subset of the items while ensuring the total weight does not exceed a given capacity.

DP Approach to Solve Knapsack Problem:

To efficiently find the maximum value we can achieve in the Knapsack problem, we use a DP table to store the maximum value that can be obtained for different capacities and subsets of items.

Create a 2D DP table of size (n+1) x (capacity+1), where n is the number of items and capacity is the given knapsack capacity.
Initialize the first row and first column of the DP table to 0. These represent the situation when either the knapsack capacity is 0 or there are no items to choose from.
Fill up the DP table row by row, starting from the second row and second column.
For each cell (i, j) in the DP table, we have two options:
- If the weight of the current item is less than or equal to the current capacity j, we can either include the item in the knapsack or exclude it. We take the maximum of these two values: dp[i][j] = max(value[i] + dp[i-1][j-weight[i]], dp[i-1][j]).
- If the weight of the current item is greater than the current capacity j, we cannot include the item, so we set dp[i][j] = dp[i-1][j].
The bottom-right cell of the DP table (n, capacity) will contain the maximum value we can achieve in the knapsack.
To find the items included in the knapsack, backtrack from the bottom-right cell to the top-left cell, following the cell’s value to decide if the item was included or not.

C++ Code for Knapsack Problem:

C++

#include <iostream>
#include <vector>

int knapsack(int capacity, const std::vector<int>& weights, const std::vector<int>& values) {
    int n = weights.size();

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

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= capacity; ++j) {
            if (weights[i - 1] <= j) {
                dp[i][j] = std::max(values[i - 1] + dp[i - 1][j - weights[i - 1]], dp[i - 1][j]);
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    return dp[n][capacity];
}

int main() {
    std::vector<int> weights = {2, 3, 4, 5};
    std::vector<int> values = {3, 4, 5, 6};
    int capacity = 5;

    std::cout << "Maximum value in Knapsack: " << knapsack(capacity, weights, values) << std::endl;
    return 0;
}

In this code, we use the DP table to store the maximum values that can be achieved for different capacities and subsets of items. The time complexity of this solution is O(n * capacity), where n is the number of items. The space complexity is also O(n * capacity) to store the DP table. The code will output the maximum value that can be obtained in the knapsack.

14. Can you explain how DP is used in the problem of counting the number of ways to cover a distance with 1, 2, and 3 steps?

Dynamic Programming (DP) can be used to efficiently count the number of ways to cover a given distance using steps of 1, 2, and 3. This problem can be solved by breaking it down into smaller overlapping subproblems and using DP to store and reuse the results of these subproblems.

Problem: Count the Number of Ways to Cover a Distance

Given a distance n, you need to find the number of ways to cover the distance using steps of 1, 2, and 3.

Example:

Let’s say the distance is 4. The number of ways to cover the distance using steps of 1, 2, and 3 are: {1, 1, 1, 1}, {1, 1, 2}, {1, 2, 1}, {2, 1, 1}, {2, 2}, and {3, 1} – a total of 6 ways.

DP Approach to Solve the Problem:

Create a DP array of size n+1 to store the number of ways to cover each distance from 0 to n.
Initialize the base cases: dp[0] = 1, since there is one way to cover a distance of 0 (by not moving).
Iterate from 1 to n and calculate dp[i] using the formula: dp[i] = dp[i-1] + dp[i-2] + dp[i-3].
The value of dp[n] will be the answer, representing the number of ways to cover the distance n using steps of 1, 2, and 3.

C++ Code for Counting the Number of Ways to Cover a Distance:

C++

#include <iostream>
#include <vector>

int countWaysToCoverDistance(int n) {
    std::vector<int> dp(n + 1, 0);

    dp[0] = 1; // Base case

    for (int i = 1; i <= n; ++i) {
        dp[i] += dp[i - 1];
        if (i >= 2) dp[i] += dp[i - 2];
        if (i >= 3) dp[i] += dp[i - 3];
    }

    return dp[n];
}

int main() {
    int distance = 4;
    std::cout << "Number of ways to cover distance " << distance << ": " << countWaysToCoverDistance(distance) << std::endl;
    return 0;
}

In this code, we use the DP array to store the number of ways to cover each distance from 0 to n. The solution is obtained by considering the ways to cover distances using steps of 1, 2, and 3, and previous subproblems. The time complexity of this solution is O(n).

15. How can DP be used to count the number of ways to reach a certain score in a game?

Problem of Counting Number of Ways to Reach a Score:
Given a score n and possible ways to score (e.g., 3, 5, and 10 points), find the number of ways to reach the score using these ways to score.

C++ Code for Counting Number of Ways to Reach a Score (Bottom-up approach – Tabulation):

C++

#include <iostream>
#include <vector>

int countWaysToReachScore(int n, const std::vector<int>& waysToScore) {
    std::vector<int> dp(n + 1, 0);

    dp[0] = 1; // Base case

    for (int i = 1; i <= n; ++i) {
        for (int way : waysToScore) {
            if (i >= way) {
                dp[i] += dp[i - way];
            }
        }
    }

    return dp[n];
}

int main() {
    int score = 12;
    std::vector<int> waysToScore = {3, 5, 10};
    std::cout << "Number of ways to reach score " << score << ": " << countWaysToReachScore(score, waysToScore) << std::endl;
    return 0;
}

In this code, the dp table is used to store the number of ways to reach scores from 0 to n. The solution is obtained by considering the possible ways to score and previous subproblems. The time complexity of this solution is O(n * m), where n is the score and m is the number of ways to score.

16. Can you explain how DP is used in the problem of finding the minimum cost path in a grid?

Problem of Finding Minimum Cost Path in a Grid:
Given a 2D grid with non-negative costs at each cell, find the minimum cost to reach the bottom-right corner from the top-left corner, moving only right or down.

C++ Code for Minimum Cost Path in a Grid (Bottom-up approach – Tabulation):

C++

#include <iostream>
#include <vector>
#include <climits>

int minCostPath(const std::vector<std::vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();

    std::vector<std::vector<int>> dp(m, std::vector<int>(n, INT_MAX));

    dp[0][0] = grid[0][0];

    for (int i = 1; i < m; ++i) {
        dp[i][0

] = dp[i - 1][0] + grid[i][0];
    }

    for (int j = 1; j < n; ++j) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }

    for (int i = 1; i < m; ++i) {
        for (int j = 1; j < n; ++j) {
            dp[i][j] = grid[i][j] + std::min(dp[i - 1][j], dp[i][j - 1]);
        }
    }

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

int main() {
    std::vector<std::vector<int>> grid = {
        {1, 3, 1},
        {1, 5, 1},
        {4, 2, 1}
    };

    std::cout << "Minimum cost path: " << minCostPath(grid) << std::endl;
    return 0;
}

In this code, the dp table is used to store the minimum cost to reach each cell from the top-left corner. The solution is obtained by considering the costs at each cell and the minimum cost paths from the previous cells. The time complexity of this solution is O(m * n), where m and n are the dimensions of the grid.

17. What is the Bellman-Ford Algorithm and how does it relate to Dynamic Programming?

The Bellman-Ford algorithm is a single-source shortest path algorithm used to find the shortest paths from a given source vertex to all other vertices in a weighted graph. It can handle graphs with negative weight edges but can also detect negative weight cycles. The algorithm is based on the principle of relaxation, where it iteratively updates the shortest distance estimates until it converges to the correct shortest paths.

Algorithm Steps:

Initialize an array of distances to all vertices from the source vertex, with the distance to the source as 0 and infinity for all other vertices.
Iterate N-1 times, where N is the number of vertices in the graph. In each iteration, consider all edges and update the distance to each vertex if a shorter path is found.
After N-1 iterations, if there are no negative weight cycles in the graph, the distance array will contain the shortest path distances from the source vertex to all other vertices.

Example:

Consider the following graph:

  (A)----1-->(B)
   |       ^   |
   |       |   2
   |       |   v
   |       +-->(C)
   |           ^
   |           |
   +---3-------+

The Bellman-Ford algorithm can find the shortest path distances from vertex A to all other vertices in this graph.

C++ Code for Bellman-Ford Algorithm:

C++

#include <iostream>
#include <vector>
#include <climits>

struct Edge {
    int source, destination, weight;
};

void bellmanFord(int V, int E, int source, const std::vector<Edge>& edges) {
    std::vector<int> distance(V, INT_MAX);
    distance[source] = 0;

    for (int i = 1; i < V; ++i) {
        for (const Edge& edge : edges) {
            int u = edge.source;
            int v = edge.destination;
            int w = edge.weight;

            if (distance[u] != INT_MAX && distance[u] + w < distance[v]) {
                distance[v] = distance[u] + w;
            }
        }
    }

    // Check for negative weight cycles
    for (const Edge& edge : edges) {
        int u = edge.source;
        int v = edge.destination;
        int w = edge.weight;

        if (distance[u] != INT_MAX && distance[u] + w < distance[v]) {
            std::cout << "Graph contains a negative weight cycle!" << std::endl;
            return;
        }
    }

    // Print shortest path distances from the source vertex
    std::cout << "Shortest path distances from vertex " << source << ":\n";
    for (int i = 0; i < V; ++i) {
        std::cout << "To vertex " << i << ": " << distance[i] << std::endl;
    }
}

int main() {
    int V = 4; // Number of vertices
    int E = 5; // Number of edges
    int source = 0; // Source vertex

    std::vector<Edge> edges = {
        {0, 1, 1},
        {0, 2, 3},
        {1, 2, 2},
        {2, 3, -6},
        {3, 1, 2}
    };

    bellmanFord(V, E, source, edges);

    return 0;
}

In this code, the distance array is used to store the shortest path distances from the source vertex to all other vertices. The algorithm iteratively relaxes the edges V-1 times to find the shortest path distances. After V-1 iterations, the distance array contains the final shortest path distances. The algorithm then checks for negative weight cycles. If there are no negative weight cycles, it prints the shortest path distances from the source vertex to all other vertices.

18. What is the Floyd Warshall Algorithm and how does it relate to Dynamic Programming? Explain with examples and code

The Floyd-Warshall algorithm is a dynamic programming-based algorithm used to find the shortest paths between all pairs of vertices in a weighted graph. It can handle graphs with both positive and negative edge weights, but it cannot detect negative weight cycles. The algorithm is based on the principle of optimal substructure, which allows it to efficiently compute the shortest paths for all pairs of vertices by considering intermediate vertices one by one.

Explanation:

Suppose we have a weighted graph with V vertices and want to find the shortest path between any two vertices i and j. The Floyd-Warshall algorithm fills up a 2D array dist of size VxV, where dist[i][j] represents the shortest distance between vertex i and vertex j. The algorithm gradually builds up the shortest distances by considering all possible intermediate vertices (k) and updating the shortest paths based on whether using vertex k as an intermediate vertex reduces the distance between vertices i and j.

Steps of the Floyd-Warshall Algorithm:

Initialize the dist array with the direct edge weights between the vertices. If there is no direct edge between i and j, set dist[i][j] to a very large value to represent infinity.
For each intermediate vertex k (from 1 to V), consider all pairs of vertices i and j, and update dist[i][j] as follows:
- If dist[i][j] > dist[i][k] + dist[k][j], update dist[i][j] to dist[i][k] + dist[k][j]. This means that using vertex k as an intermediate vertex reduces the distance between i and j, so we update the shortest path accordingly.
Continue this process for all possible intermediate vertices.

C++ Code for Floyd-Warshall Algorithm:

C++

#include <iostream>
#include <vector>
#include <climits>

void floydWarshall(std::vector<std::vector<int>>& graph) {
    int V = graph.size();

    for (int k = 0; k < V; ++k) {
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < V; ++j) {
                if (graph[i][k] != INT_MAX && graph[k][j] != INT_MAX && graph[i][k] + graph[k][j] < graph[i][j]) {
                    graph[i][j] = graph[i][k] + graph[k][j];
                }
            }
        }
    }
}

int main() {
    int V = 4;
    std::vector<std::vector<int>> graph = {
        {0, 5, INT_MAX, 10},
        {INT_MAX, 0, 3, INT_MAX},
        {INT_MAX, INT_MAX, 0, 1},
        {INT_MAX, INT_MAX, INT_MAX, 0}
    };

    floydWarshall(graph);

    std::cout << "Shortest distances between all pairs of vertices:\n";
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            if (graph[i][j] == INT_MAX) {
                std::cout << "INF\t";
            } else {
                std::cout << graph[i][j] << "\t";
            }
        }
        std::cout << std::endl;
    }

    return 0;
}

In this code, the graph matrix represents the weighted graph. The floydWarshall function applies the Floyd-Warshall algorithm to find the shortest distances between all pairs of vertices. The time complexity of this algorithm is O(V^3), where V is the number of vertices in the graph, making it efficient for dense graphs. The space complexity is O(V^2) to store the dist matrix.

19. What are the limitations of Dynamic Programming?

While Dynamic Programming is a powerful technique, it has some limitations:

Overhead: DP can involve significant overhead in maintaining and filling up the table of subproblem results, leading to higher memory consumption.
State Space: For some problems, the state space (parameters that define a subproblem) can be large, leading to a very large table and increased memory requirements.
Not Suitable for All Problems: Not all problems can be efficiently solved using DP. Some problems may not exhibit the optimal substructure or overlapping subproblems required for DP to be effective.

Example – Fibonacci Series using Naive Recursion:

C++

#include <iostream>

int fibonacciRecursive(int n) {
    if (n <= 1)
        return n;
    return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);
}

int main() {
    int n = 40;
    std::cout << "Fibonacci(" << n << ") using recursion: " << fibonacciRecursive(n) << std::endl;
    return 0;
}

In this code, calculating the 40th Fibonacci number using naive recursion is extremely slow and inefficient due to redundant calculations.

20. Can you explain the term ‘state-space reduction’ in the context of DP?

State-space reduction is a technique used in DP to reduce the size of the table (state space) needed to store subproblem results. It involves eliminating unnecessary or redundant states from the table.

Example – Coin Change Problem with State-space Reduction:
The Coin Change problem involves finding the minimum number of coins needed to make a given amount of money. To reduce the state space, we can initialize the DP table with a very large value (e.g., INT_MAX) and only update the table for valid states.

C++ Code for Coin Change Problem with State-space Reduction:

C++

#include <iostream>
#include <vector>
#include <climits>

int coinChange(const std::vector<int>& coins, int amount) {
    std::vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0; // Base case

    for (int coin : coins) {
        for (int i = coin; i <= amount; ++i) {
            if (dp[i - coin] != INT_MAX) {
                dp[i] = std::min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return

 dp[amount] == INT_MAX ? -1 : dp[amount];
}

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

In this code, we only update the DP table for states that are reachable using the given coins. States that cannot be reached will remain with their initial value of INT_MAX, reducing the size of the state space.

Coding Questions

1. Implement a solution for the 0/1 knapsack problem.

C++

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

int knapsack(int W, vector<int>& weights, vector<int>& values, int n) {
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][W];
}

int main() {
    int W = 50;
    vector<int> weights = {10, 20, 30};
    vector<int> values = {60, 100, 120};
    int n = weights.size();

    int maxVal = knapsack(W, weights, values, n);
    cout << "Maximum value: " << maxVal << endl;

    return 0;
}

2. Implement a solution for the unbounded knapsack problem.

C++

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

int unboundedKnapsack(int W, vector<int>& weights, vector<int>& values, int n) {
    vector<int> dp(W + 1, 0);

    for (int w = 1; w <= W; w++) {
        for (int i = 0; i < n; i++) {
            if (weights[i] <= w) {
                dp[w] = max(dp[w], values[i] + dp[w - weights[i]]);
            }
        }
    }

    return dp[W];
}

int main() {
    int W = 100;
    vector<int> weights = {10, 20, 30};
    vector<int> values = {60, 100, 120};
    int n = weights.size();

    int maxVal = unboundedKnapsack(W, weights, values, n);
    cout << "Maximum value: " << maxVal << endl;

    return 0;
}

3. Write a program to find the longest common subsequence.

C++

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

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.length();
    int n = text2.length();

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

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1[i - 1] == text2[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[m][n];
}

int main() {
    string text1 = "abcde";
    string text2 = "ace";

    int length = longestCommonSubsequence(text1, text

2);
    cout << "Length of longest common subsequence: " << length << endl;

    return 0;
}

4. Write a program to find the longest increasing subsequence.

C++

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

int longestIncreasingSubsequence(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] = max(dp[i], dp[j] + 1);
            }
        }
    }

    int maxLength = 0;
    for (int i = 0; i < n; i++) {
        maxLength = max(maxLength, dp[i]);
    }

    return maxLength;
}

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

    int length = longestIncreasingSubsequence(nums);
    cout << "Length of longest increasing subsequence: " << length << endl;

    return 0;
}

5. Implement a solution to find the minimum number of coins needed to make a change.

C++

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

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, INT_MAX);
    dp[0] = 0;

    for (int i = 1; i <= amount; i++) {
        for (int coin : coins) {
            if (coin <= i && dp[i - coin] != INT_MAX) {
                dp[i] = min(dp[i], dp[i - coin] + 1);
            }
        }
    }

    return (dp[amount] == INT_MAX) ? -1 : dp[amount];
}

int main() {
    vector<int> coins = {1, 2, 5};
    int amount = 11;

    int minCoins = coinChange(coins, amount);
    cout << "Minimum number of coins needed: " << minCoins << endl;

    return 0;
}

6. Write a program to find the number of ways to decode a message given a coding scheme (A->1, B->2, …, Z->26).

C++

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

int numDecodings(string s) {
    int n = s.length();
    if (n == 0 || s[0] == '0') {
        return 0;
    }

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

    for (int i = 2; i <= n; i++) {
        int oneDigit = stoi(s.substr(i - 1, 1));
        int twoDigits = stoi(s.substr(i - 2, 2));

        if (oneDigit >= 1) {
            dp[i] += dp[i - 1];
        }
        if (twoDigits >= 10 && twoDigits <= 26) {
            dp[i] += dp[i - 2];
        }
    }

    return dp[n];
}

int main() {
    string message = "226";

    int ways = numDecodings(message);
    cout << "Number of ways to decode the message: " << ways << endl;

    return 0;
}

7. Implement a solution to find the longest palindrome subsequence.

C++

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

int longestPalindromeSubsequence(string s) {
    int n = s.length();
    vector<vector<int>> dp(n, vector<int>(n, 0));

    for (int i = 0; i < n; i++) {
        dp[i][i] = 1;
    }

    for (int len = 2; len <= n; len++) {
        for (int i = 0; i < n - len + 1; i++) {
            int j = i + len - 1;
            if (s[i] == s[j] && len == 2) {
                dp[i][j] = 2;
            } else if (s[i] == s[j]) {
                dp[i][j] = dp[i + 1][j - 1] + 2;
            } else {
                dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
            }
        }
    }

    return dp[0][n - 1];
}

int main() {
    string s = "bbbab";

    int length = longestPalindromeSubsequence(s);
    cout << "Length of the longest palindrome subsequence: " << length << endl;

    return 0;
}

8. Implement a solution to find the longest palindrome substring.

C++

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

string longestPalindromeSubstring(string s) {
    int n = s.length();
    vector<vector<bool>> dp(n, vector<bool>(n, false));

    int maxLength = 1;
    int start = 0;

    for (int i = 0; i < n; i++) {
        dp[i][i] = true;
    }

    for (int i = 0; i < n - 1; i++) {
        if (s[i] == s[i + 1]) {
            dp[i][i + 1] = true;
            start = i;
            maxLength = 2;
        }
    }

    for (int len =

 3; len <= n; len++) {
        for (int i = 0; i < n - len + 1; i++) {
            int j = i + len - 1;
            if (s[i] == s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                if (len > maxLength) {
                    maxLength = len;
                    start = i;
                }
            }
        }
    }

    return s.substr(start, maxLength);
}

int main() {
    string s = "babad";

    string longestPalindrome = longestPalindromeSubstring(s);
    cout << "Longest palindrome substring: " << longestPalindrome << endl;

    return 0;
}

9. Implement a solution to solve the Rod Cutting Problem.

C++

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

int rodCutting(vector<int>& prices, int n) {
    vector<int> dp(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            dp[i] = max(dp[i], prices[j - 1] + dp[i - j]);
        }
    }

    return dp[n];
}

int main() {
    vector<int> prices = {1, 5, 8, 9, 10, 17, 17, 20};
    int length = 8;

    int maxProfit = rodCutting(prices, length);
    cout << "Maximum profit: " << maxProfit << endl;

    return 0;
}

10. Write a program to find the minimum cost path in a grid.

C++

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

int minCostPath(vector<vector<int>>& grid) {
    int m = grid.size();
    int n = grid[0].size();

    vector<vector<int>> dp(m, vector<int>(n, 0));
    dp[0][0] = grid[0][0];

    for (int i = 1; i < m; i++) {
        dp[i][0] = dp[i - 1][0] + grid[i][0];
    }

    for (int j = 1; j < n; j++) {
        dp[0][j] = dp[0][j - 1] + grid[0][j];
    }

    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = grid[i][j] + min(dp[i - 1][j], dp[i][j - 1]);
        }
    }

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

int main() {
    vector<vector<int>> grid = {{1, 3, 1},
                                {1, 5, 1},
                                {4, 2, 1}};

    int minCost = minCostPath(grid);
    cout << "Minimum cost path: " << minCost << endl;

    return 0;
}

11. Write a program to count the number of ways to cover a distance with 1, 2, and 3 steps.

C++

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

int countWaysToCoverDistance(int distance) {
    vector<int> dp(distance + 1, 0);
    dp[0] = 1;

    for (int i = 1; i <= distance; i++) {
        if (i >= 1)
            dp[i] += dp[i - 1];
        if (i >= 2)
            dp[i] += dp[i - 2];
        if (i >= 3)
            dp[i] += dp[i - 3];
    }

    return dp[distance];
}

int main() {
    int distance = 4;

    int ways = countWaysToCoverDistance(distance);
    cout << "Number of ways to cover distance " << distance << " is: " << ways << endl;

    return 0;
}

12. Write a program to find the optimal strategy for a game.

C++

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

int optimalGameStrategy(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));

    for (int i = 0; i < n; i++) {
        dp[i][i] = nums[i];
    }

    for (int len = 2; len <= n; len++) {
        for (int i = 0; i < n - len + 1; i++) {
            int j = i + len - 1;
            int left = nums[i] + min(dp[i + 2][j], dp[i + 1][j - 1]);
            int right = nums[j] + min(dp[i + 1][j - 1], dp[i][j - 2]);
            dp[i][j] = max(left, right);
        }
    }

    return dp[0][n - 1];
}

int main() {
    vector<int> nums = {5, 3, 7, 10};

    int maxScore = optimalGameStrategy(nums);
    cout << "Maximum score: " << maxScore << endl;

    return 0;
}

13. Write a program to solve the Egg Dropping Puzzle.

C++

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

int eggDroppingPuzzle(int eggs, int floors) {
    vector<vector<int>> dp(eggs + 1, vector<int>(floors + 1, 0));

    for (int i = 1; i <= eggs; i++) {
        dp[i][1] = 1;
        dp[i][0] = 0;
    }

    for (int j = 1; j <= floors; j++) {
        dp[1][j] = j;
    }

    for (int i = 2; i <= eggs; i++) {
        for (int j = 2; j <= floors; j++) {
            dp[i][j] = INT_MAX;
            for (int k = 1; k <= j; k++) {
                int attempts = 1 + max(dp[i - 1][k - 1], dp[i][j - k]);
                dp[i][j] = min(dp[i][j], attempts);
            }
        }
    }

    return dp[eg

gs][floors];
}

int main() {
    int eggs = 2;
    int floors = 10;

    int minAttempts = eggDroppingPuzzle(eggs, floors);
    cout << "Minimum number of attempts: " << minAttempts << endl;

    return 0;
}

14. Implement a solution to find the maximum length chain of pairs.

C++

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

struct Pair {
    int first;
    int second;
};

bool comparePairs(const Pair& p1, const Pair& p2) {
    return p1.second < p2.second;
}

int maxChainLength(vector<Pair>& pairs) {
    int n = pairs.size();
    vector<int> dp(n, 1);

    sort(pairs.begin(), pairs.end(), comparePairs);

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (pairs[i].first > pairs[j].second && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
    }

    return *max_element(dp.begin(), dp.end());
}

int main() {
    vector<Pair> pairs = {{5, 24},
                          {15, 25},
                          {27, 40},
                          {50, 60}};

    int maxLength = maxChainLength(pairs);
    cout << "Maximum chain length: " << maxLength << endl;

    return 0;
}

15. Write a program to find the maximum sum increasing subsequence.

C++

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

int maxSumIncreasingSubsequence(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 0);
    int maxSum = nums[0];

    for (int i = 0; i < n; i++) {
        dp[i] = nums[i];
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + nums[i]);
            }
        }
        maxSum = max(maxSum, dp[i]);
    }

    return maxSum;
}

int main() {
    vector<int> nums = {1, 101, 2, 3, 100, 4, 5};

    int maxSum = maxSumIncreasingSubsequence(nums);
    cout << "Maximum sum of increasing subsequence: " << maxSum << endl;

    return 0;
}

16. Write a program to solve the Matrix Chain Multiplication problem.

C++

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

int matrixChainMultiplication(vector<int>& dimensions) {
    int n = dimensions.size();
    vector<vector<int>> dp(n, vector<int>(n, 0));

    for (int len = 2; len < n; len++) {
        for (int i = 1; i < n - len + 1; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
            for (int k = i; k < j; k++) {
                int cost = dp[i][k] + dp[k + 1][j] + dimensions[i - 1] * dimensions[k] * dimensions[j];
                dp[i][j] = min(dp[i][j], cost);
            }
        }
    }

    return

 dp[1][n - 1];
}

int main() {
    vector<int> dimensions = {10, 30, 5, 60};

    int minMultiplications = matrixChainMultiplication(dimensions);
    cout << "Minimum number of multiplications: " << minMultiplications << endl;

    return 0;
}

17. Write a program to find the maximum value of an expression.

C++

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

int evaluateExpression(char op, int a, int b) {
    switch (op) {
        case '+':
            return a + b;
        case '-':
            return a - b;
        case '*':
            return a * b;
    }
    return 0;
}

int maxExpressionValue(string& expression) {
    int n = expression.length();
    vector<vector<int>> dp(n, vector<int>(n, 0));

    for (int i = 0; i < n; i += 2) {
        dp[i][i] = expression[i] - '0';
    }

    for (int len = 3; len <= n; len += 2) {
        for (int i = 0; i < n - len + 1; i += 2) {
            int j = i + len - 1;
            dp[i][j] = INT_MIN;
            for (int k = i + 1; k < j; k += 2) {
                int left = evaluateExpression(expression[k], dp[i][k - 1], dp[k + 1][j]);
                dp[i][j] = max(dp[i][j], left);
            }
        }
    }

    return dp[0][n - 1];
}

int main() {
    string expression = "1+2*3+4*5";

    int maxValue = maxExpressionValue(expression);
    cout << "Maximum value of expression: " << maxValue << endl;

    return 0;
}

18. Implement a solution to solve the Word Break problem.

C++

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

bool wordBreak(string s, unordered_set<string>& wordSet) {
    int n = s.length();
    vector<bool> dp(n + 1, false);
    dp[0] = true;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (dp[j] && wordSet.count(s.substr(j, i - j)) > 0) {
                dp[i] = true;
                break;
            }
        }
    }

    return dp[n];
}

int main() {
    string s = "leetcode";
    unordered_set<string> wordSet = {"leet", "code"};

    bool isBreakable = wordBreak(s, wordSet);
    cout << "Word Break possible? " << (isBreakable ? "Yes" : "No") << endl;

    return 0;
}

19. Write a program to solve the Edit Distance problem.

C++

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

int minEditDistance(string& word1, string& word2) {
    int m = word1.length();
    int n = word2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = 0; i <= m; i++) {
        dp[i][0] = i;
    }

    for (int

 j = 0; j <= n; j++) {
        dp[0][j] = j;
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1[i - 1] == word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = min({dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]}) + 1;
            }
        }
    }

    return dp[m][n];
}

int main() {
    string word1 = "intention";
    string word2 = "execution";

    int minDistance = minEditDistance(word1, word2);
    cout << "Minimum edit distance: " << minDistance << endl;

    return 0;
}

20. Implement a solution for the Coin Change Problem.

C++

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

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);
    dp[0] = 0;

    for (int i = 1; i <= amount; i++) {
        for (int j = 0; j < coins.size(); j++) {
            if (coins[j] <= i) {
                dp[i] = min(dp[i], dp[i - coins[j]] + 1);
            }
        }
    }

    return dp[amount] <= amount ? dp[amount] : -1;
}

int main() {
    vector<int> coins = {1, 2, 5};
    int amount = 11;

    int minCoins = coinChange(coins, amount);
    cout << "Minimum number of coins required: " << minCoins << endl;

    return 0;
}

21. Implement a solution for the Subset Sum Problem.

C++

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

bool subsetSum(vector<int>& nums, int target) {
    int n = nums.size();
    vector<vector<bool>> dp(n + 1, vector<bool>(target + 1, false));

    for (int i = 0; i <= n; i++) {
        dp[i][0] = true;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= target; j++) {
            if (nums[i - 1] <= j) {
                dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }

    return dp[n][target];
}

int main() {
    vector<int> nums = {2, 3, 7, 8, 10};
    int target = 11;

    bool isSubsetSum = subsetSum(nums, target);
    cout << "Subset Sum possible? " << (isSubsetSum ? "Yes" : "No") << endl;

    return 0;
}

22. Write a program to solve the Assembly Line Scheduling problem.

C++

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

int assemblyLineScheduling(vector<vector<int>>& times, vector<vector<int>>& transferTimes,
                           vector<int>& entryTimes, vector<int>& exitTimes) {
    int n = times[0].size();
    vector<int> dp1(n, 0);
    vector<int> dp2(n, 0);

    dp1[0] = entryTimes[0] + times[0][0];
    dp2[0] = entryTimes[1] + times[1][0];

    for (int i = 1; i < n; i++) {
        dp1[i] = min(dp1[i - 1] + times[0][i], dp2[i - 1] + times[0][i] + transferTimes[1][i]);
        dp2[i] = min(dp2[i - 1] + times[1][i], dp1[i - 1] + times[1][i] + transferTimes[0][i]);
    }

    return min(dp1[n - 1] + exitTimes[0], dp2[n - 1] + exitTimes[1]);
}

int main() {
    vector<vector<int>> times = {{4, 5, 3, 2}, {2, 10, 1, 4}};
    vector<vector<int>> transferTimes = {{0, 7, 4, 5}, {0, 9, 2, 8}};
    vector<int> entryTimes = {10, 12};
    vector<int> exitTimes = {18, 7};

    int minTime = assemblyLineScheduling(times, transferTimes, entryTimes, exitTimes);
    cout << "Minimum time: " << minTime << endl;

    return 0;
}

23. Implement a solution to solve the Travelling Salesman Problem.

C++

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

const int INF = numeric_limits<int>::max();

int tsp(vector<vector<int>>& graph, int mask, int pos, vector<vector<int>>& dp) {
    int n = graph.size();
    if (mask == (1 << n) - 

1) {
        return graph[pos][0];
    }

    if (dp[mask][pos] != -1) {
        return dp[mask][pos];
    }

    int ans = INF;
    for (int city = 0; city < n; city++) {
        if ((mask & (1 << city)) == 0) {
            int cost = graph[pos][city] + tsp(graph, mask | (1 << city), city, dp);
            ans = min(ans, cost);
        }
    }

    return dp[mask][pos] = ans;
}

int travelingSalesmanProblem(vector<vector<int>>& graph) {
    int n = graph.size();
    vector<vector<int>> dp(1 << n, vector<int>(n, -1));

    return tsp(graph, 1, 0, dp);
}

int main() {
    vector<vector<int>> graph = {{0, 10, 15, 20},
                                 {10, 0, 35, 25},
                                 {15, 35, 0, 30},
                                 {20, 25, 30, 0}};

    int minDistance = travelingSalesmanProblem(graph);
    cout << "Minimum distance: " << minDistance << endl;

    return 0;
}

24. Write a program to solve the Longest Common Substring problem.

C++

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

int longestCommonSubstring(string& s1, string& s2) {
    int m = s1.length();
    int n = s2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    int maxLen = 0;

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
                maxLen = max(maxLen, dp[i][j]);
            } else {
                dp[i][j] = 0;
            }
        }
    }

    return maxLen;
}

int main() {
    string s1 = "abcdxyz";
    string s2 = "xyzabcd";

    int longestLen = longestCommonSubstring(s1, s2);
    cout << "Longest common substring length: " << longestLen << endl;

    return 0;
}

25. Write a program to find the minimum number of deletions to make a string palindrome.

C++

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

int minDeletionsToMakePalindrome(string& s) {
    string rev = s;
    reverse(rev.begin(), rev.end());

    int n = s.length();
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (s[i - 1] == rev[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return n - dp[n][n];
}

int main() {
    string s = "abcbda";

    int minDeletions = minDeletions

ToMakePalindrome(s);
    cout << "Minimum deletions: " << minDeletions << endl;

    return 0;
}

26. Implement a solution to find the maximum sum of a subsequence with no adjacent elements.

C++

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

int maxSubsetSumNoAdjacent(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) {
        return 0;
    }

    if (n == 1) {
        return nums[0];
    }

    int first = nums[0];
    int second = max(nums[0], nums[1]);

    for (int i = 2; i < n; i++) {
        int curr = max(second, first + nums[i]);
        first = second;
        second = curr;
    }

    return second;
}

int main() {
    vector<int> nums = {4, 1, 1, 9, 1};

    int maxSum = maxSubsetSumNoAdjacent(nums);
    cout << "Maximum sum of subsequence: " << maxSum << endl;

    return 0;
}

27. Write a program to solve the Longest Repeated Subsequence problem.

C++

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

int longestRepeatedSubsequence(string& s) {
    int n = s.length();
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (s[i - 1] == s[j - 1] && i != j) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    return dp[n][n];
}

int main() {
    string s = "AABEBCDD";

    int longestLen = longestRepeatedSubsequence(s);
    cout << "Longest repeated subsequence length: " << longestLen << endl;

    return 0;
}

28. Implement a solution to solve the Optimal Binary Search Tree problem.

C++

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

const int INF = numeric_limits<int>::max();

int optimalBST(vector<int>& keys, vector<int>& freq) {
    int n = keys.size();
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
    vector<vector<int>> cost(n + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= n; i++) {
        dp[i][i] = freq[i - 1];
        cost[i][i] = keys[i - 1] * freq[i - 1];
    }

    for (int L = 2; L <= n; L++) {
        for (int i = 1; i <= n - L + 1; i++) {
            int j = i + L - 1;
            dp[i][j] = INF;

            for (int k = i; k <= j; k++) {
                int c = (k > i) ? dp[i][k - 1] + dp[k + 1][j] : 0;
                if (c < dp[i][j]) {
                    dp[i][j] = c;
                    cost[i][j] = cost[i][k - 1] + cost[k + 1][j] + (keys[k - 1] * freq[k - 1]);
                }
            }
        }
    }

    return cost[1][n];
}

int main() {
    vector<int> keys = {10, 20, 30};
    vector<int> freq = {2, 3, 1};

    int minCost = optimalBST(keys, freq);
    cout << "Minimum cost of optimal BST: " << minCost << endl;

    return 0;
}

29. Write a program to find the minimum number of jumps to reach the end of an array.

C++

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

const int INF = numeric_limits<int>::max();

int minJumpsToEnd(vector<int>& nums) {
    int n = nums.size();
    vector<int> jumps(n, INF);

    jumps[0] = 0;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (j + nums[j] >= i && jumps[j] != INF) {
                jumps[i] = min(jumps[i], jumps[j] + 1);
            }
        }
    }

    return jumps[n - 1];
}

int main() {
    vector<int> nums = {3, 4, 2, 1, 2, 3, 7, 1, 1, 1, 3};

    int minJumps = minJumpsToEnd(nums);
    cout << "Minimum number of jumps: " << minJumps << endl;

    return 0;
}

30. Write a program to find the maximum length of a pair chain.

C++

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

int findLongestChain(vector<vector<int>>& pairs) {
    sort(pairs.begin(), pairs.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[1] < b[1];
    });

    int n = pairs.size();
    int count = 1;
    int currEnd = pairs[0][1];

    for (int i = 1; i < n; i++) {
        if (pairs[i][0] > currEnd) {
            count++;
            currEnd = pairs[i][1];
        }
    }

    return count;
}

int main() {
    vector<vector<int>> pairs = {{1, 2}, {2, 3}, {3, 4}, {4, 5}};

    int maxLength = findLongestChain(pairs);
    cout << "Maximum length of pair chain: " << maxLength << endl;

    return 0;
}

31. Implement a solution to find the shortest common supersequence.

C++

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

string shortestCommonSupersequence(string& str1, string& str2) {
    int m = str1.length();
    int n = str2.length();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (str1[i - 1] == str2[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    string superseq;
    int i = m, j = n;

    while (i > 0 && j > 0) {
        if (str1[i - 1] == str2[j - 1]) {
            superseq.push_back(str1[i - 1]);
            i--;
            j--;
        } else if (dp[i - 1][j] > dp[i][j - 1]) {
            superseq.push_back(str1[i - 1]);
            i--;
        } else {
            superseq.push_back(str2[j - 1]);
            j--;
        }
    }

    while (i > 0) {
        superseq.push_back(str1[i - 1]);
        i--;
    }

    while (j > 0) {
        superseq.push_back(str2[j - 1]);
        j--;
    }

    reverse(superseq.begin(), superseq.end());

    return superseq;
}

int main() {
    string str1 = "ABCBDAB";
    string str2 = "BDCAB";

    string superseq = shortestCommonSupersequence(str1, str2);
    cout << "Shortest common supersequence: " << superseq << endl;

    return 0;
}

32. Write a program to solve the Box Stacking problem.

C++

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

struct Box {
    int length;
    int width;
    int height;
};

bool compareBoxes(const Box& b1, const Box& b2) {
    return (b1.length * b1.width) > (b2.length * b2.width);
}

int maxHeightOfBoxStacking(vector<Box>& boxes) {
    vector<Box> rotations;
    int n = boxes.size();

    for (int i = 0; i < n; i++) {
        Box box1 = boxes[i];
        rotations.push_back(box1);

        Box box2 = {box1.width, box1.height, box1.length};
        rotations.push_back(box2);

        Box box3 = {box1.height, box1.length, box1.width};
        rotations.push_back(box3);
    }

    sort(rotations.begin(), rotations.end(), compareBoxes);

    vector<int> dp(n * 3, 0);

    for (int i = 0; i < n * 3; i++) {
        dp[i] = rotations[i].height;
    }

    for (int i = 1; i < n * 3; i++) {
        for (int j = 0; j < i; j++) {
            if (rotations[i].length < rotations[j].length &&
                rotations[i].width < rotations[j].width) {


 dp[i] = max(dp[i], dp[j] + rotations[i].height);
            }
        }
    }

    int maxHeight = 0;
    for (int i = 0; i < n * 3; i++) {
        maxHeight = max(maxHeight, dp[i]);
    }

    return maxHeight;
}

int main() {
    vector<Box> boxes = {{4, 6, 7}, {1, 2, 3}, {4, 5, 6}, {10, 12, 32}};

    int maxHeight = maxHeightOfBoxStacking(boxes);
    cout << "Max height of box stacking: " << maxHeight << endl;

    return 0;
}

33. Write a program to find the minimum number of deletions to make a sequence sorted.

C++

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

int minDeletionsToSort(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] = max(dp[i], dp[j] + 1);
            }
        }
    }

    int maxLen = *max_element(dp.begin(), dp.end());
    int minDeletions = n - maxLen;

    return minDeletions;
}

int main() {
    vector<int> nums = {4, 2, 3, 6, 10, 1, 12};

    int minDeletions = minDeletionsToSort(nums);
    cout << "Minimum number of deletions: " << minDeletions << endl;

    return 0;
}

34. Implement a solution to solve the Text Justification problem.

C++

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

vector<string> justifyText(vector<string>& words, int maxWidth) {
    vector<string> result;
    int n = words.size();
    int i = 0;

    while (i < n) {
        int j = i + 1;
        int currWidth = words[i].length();

        while (j < n && (currWidth + words[j].length() + (j - i - 1)) < maxWidth) {
            currWidth += words[j].length();
            j++;
        }

        int numWords = j - i;
        int numSpaces = maxWidth - currWidth;

        if (numWords == 1 || j >= n) {
            string line = words[i];

            for (int k = i + 1; k < j; k++) {
                line += " " + words[k];
            }

            line += string(numSpaces, ' ');
            result.push_back(line);
        } else {
            int spacesBetweenWords = floor(numSpaces / (numWords - 1));
            int extraSpaces = numSpaces % (numWords - 1);

            string line = words[i];

            for (int k = i + 1; k < j; k++) {
                int spaces = spacesBetweenWords;

                if (extraSpaces > 0) {
                    spaces++;
                    extraSpaces--;
                }

                line += string(spaces, ' ') + words[k];
            }

            result.push_back(line);
        }

        i = j;
    }

    return result;
}

int main() {
    vector<string> words = {"This", "is", "an", "example", "of", "text",

 "justification."};
    int maxWidth = 16;

    vector<string> justifiedText = justifyText(words, maxWidth);

    for (const auto& line : justifiedText) {
        cout << line << endl;
    }

    return 0;
}

35. Implement a solution to solve the Paint House problem.

C++

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

int minCostToPaintHouses(vector<vector<int>>& costs) {
    int n = costs.size();

    if (n == 0) {
        return 0;
    }

    int k = costs[0].size();

    vector<vector<int>> dp(n, vector<int>(k, 0));

    for (int j = 0; j < k; j++) {
        dp[0][j] = costs[0][j];
    }

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < k; j++) {
            dp[i][j] = costs[i][j] + min(dp[i - 1][(j + 1) % k], dp[i - 1][(j + 2) % k]);
        }
    }

    int minCost = INT_MAX;

    for (int j = 0; j < k; j++) {
        minCost = min(minCost, dp[n - 1][j]);
    }

    return minCost;
}

int main() {
    vector<vector<int>> costs = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};

    int minCost = minCostToPaintHouses(costs);
    cout << "Minimum cost to paint houses: " << minCost << endl;

    return 0;
}

36. Write a program to find the largest independent set in a binary tree.

C++

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int value) : val(value), left(nullptr), right(nullptr) {}
};

int largestIndependentSet(TreeNode* root) {
    if (root == nullptr) {
        return 0;
    }

    int sizeIncludingRoot = 1;

    if (root->left != nullptr) {
        sizeIncludingRoot += largestIndependentSet(root->left->left) +
                             largestIndependentSet(root->left->right);
    }

    if (root->right != nullptr) {
        sizeIncludingRoot += largestIndependentSet(root->right->left) +
                             largestIndependentSet(root->right->right);
    }

    int sizeExcludingRoot = largestIndependentSet(root->left) +
                            largestIndependentSet(root->right);

    return max(sizeIncludingRoot, sizeExcludingRoot);
}

int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    int largestSetSize = largestIndependentSet(root);
    cout << "Largest Independent Set Size: " << largestSetSize << endl;

    return 0;
}

37. Implement a solution to solve the Cutting a Rod problem.

C++

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

int cutRod(vector<int>& prices, int length) {
    int n = prices.size();
    vector<int> dp(length + 1, 0);

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

 (int j = 0; j < i && j < n; j++) {
            dp[i] = max(dp[i], prices[j] + dp[i - j - 1]);
        }
    }

    return dp[length];
}

int main() {
    vector<int> prices = {1, 5, 8, 9, 10, 17, 17, 20};

    int length = 8;
    int maxProfit = cutRod(prices, length);

    cout << "Maximum profit: " << maxProfit << endl;

    return 0;
}

38. Write a program to solve the Palindrome Partitioning problem.

C++

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

bool isPalindrome(const string& str, int start, int end) {
    while (start < end) {
        if (str[start] != str[end]) {
            return false;
        }
        start++;
        end--;
    }
    return true;
}

void partitionPalindromeHelper(const string& str, int start, vector<string>& partition, vector<vector<string>>& result) {
    if (start == str.length()) {
        result.push_back(partition);
        return;
    }

    for (int i = start; i < str.length(); i++) {
        if (isPalindrome(str, start, i)) {
            partition.push_back(str.substr(start, i - start + 1));
            partitionPalindromeHelper(str, i + 1, partition, result);
            partition.pop_back();
        }
    }
}

vector<vector<string>> partitionPalindrome(const string& str) {
    vector<vector<string>> result;
    vector<string> partition;
    partitionPalindromeHelper(str, 0, partition, result);
    return result;
}

int main() {
    string str = "aab";

    vector<vector<string>> partitions = partitionPalindrome(str);

    cout << "Palindrome Partitions:" << endl;
    for (const auto& partition : partitions) {
        for (const auto& word : partition) {
            cout << word << " ";
        }
        cout << endl;
    }

    return 0;
}

39. Implement a solution to find the longest path in a matrix.

C++

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

int longestPathInMatrix(vector<vector<int>>& matrix, int i, int j, vector<vector<int>>& dp) {
    int n = matrix.size();
    int m = matrix[0].size();

    if (dp[i][j] != -1) {
        return dp[i][j];
    }

    int maxPath = 1;

    if (i > 0 && matrix[i][j] < matrix[i - 1][j]) {
        maxPath = max(maxPath, 1 + longestPathInMatrix(matrix, i - 1, j, dp));
    }

    if (i < n - 1 && matrix[i][j] < matrix[i + 1][j]) {
        maxPath = max(maxPath, 1 + longestPathInMatrix(matrix, i + 1, j, dp));
    }

    if (j > 0 && matrix[i][j] < matrix[i][j - 1]) {
        maxPath = max(maxPath, 1 + longestPathInMatrix(matrix, i, j - 1, dp));
    }

    if (j < m - 1 && matrix[i][j] < matrix[i][j + 1]) {
        maxPath = max(maxPath, 1 + longestPathInMatrix(matrix, i, j + 1, dp));
    }

    dp[i][j] =

 maxPath;
    return maxPath;
}

int longestIncreasingPathInMatrix(vector<vector<int>>& matrix) {
    int n = matrix.size();
    int m = matrix[0].size();

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

    int longestPath = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            longestPath = max(longestPath, longestPathInMatrix(matrix, i, j, dp));
        }
    }

    return longestPath;
}

int main() {
    vector<vector<int>> matrix = {{9, 9, 4}, {6, 6, 8}, {2, 1, 1}};

    int longestPath = longestIncreasingPathInMatrix(matrix);
    cout << "Longest increasing path: " << longestPath << endl;

    return 0;
}

40. Write a program to solve the Optimal Game Strategy problem.

C++

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

int optimalGameStrategy(vector<int>& nums) {
    int n = nums.size();
    vector<vector<int>> dp(n, vector<int>(n));

    for (int i = 0; i < n; i++) {
        dp[i][i] = nums[i];
    }

    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
        }
    }

    return dp[0][n - 1];
}

int main() {
    vector<int> nums = {3, 9, 1, 2};

    int maxScore = optimalGameStrategy(nums);
    cout << "Maximum score: " << maxScore << endl;

    return 0;
}

41. Write a program to solve the Count All Possible Paths problem.

C++

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

int countAllPossiblePaths(int m, int n) {
    vector<vector<int>> dp(m, vector<int>(n, 0));

    for (int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }

    for (int j = 0; j < n; j++) {
        dp[0][j] = 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];
}

int main() {
    int m = 3;
    int n = 3;

    int numPaths = countAllPossiblePaths(m, n);
    cout << "Number of possible paths: " << numPaths << endl;