Table of Contents

- Introduction
- Questions
- 1. What is Dynamic Programming (DP)?
- 2. How is dynamic programming different from recursion and divide-and-conquer?
- 3. What are the key features of a problem that make it suitable for using DP in its solution?
- 4. What are the steps to solve a DP problem?
- 5. What are the main elements of a Dynamic Programming problem?
- 6. What is the concept of overlapping subproblems in Dynamic Programming?
- 7. Explain the concept of optimal substructure in DP. Explain with examples and code
- 8. What is the difference between top-down (memoization) and bottom-up (tabulation) approaches in DP?
- 9. What is ‘state’ in DP?
- 10. What is the time and space complexity of a dynamic programming algorithm?
- 11. What do you understand by ‘memoization’ in dynamic programming?
- 12. Can you explain how DP is used in the Longest Common Subsequence problem?
- 13. Can you explain how DP is used in the Knapsack problem?
- 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?
- 15. How can DP be used to count the number of ways to reach a certain score in a game?
- 16. Can you explain how DP is used in the problem of finding the minimum cost path in a grid?
- 17. What is the Bellman-Ford Algorithm and how does it relate to Dynamic Programming?
- 18. What is the Floyd Warshall Algorithm and how does it relate to Dynamic Programming? Explain with examples and code
- 19. What are the limitations of Dynamic Programming?
- 20. Can you explain the term ‘state-space reduction’ in the context of DP?
- Coding Questions
- 1. Implement a solution for the 0/1 knapsack problem.
- 2. Implement a solution for the unbounded knapsack problem.
- 3. Write a program to find the longest common subsequence.
- 4. Write a program to find the longest increasing subsequence.
- 5. Implement a solution to find the minimum number of coins needed to make a change.
- 6. Write a program to find the number of ways to decode a message given a coding scheme (A->1, B->2, …, Z->26).
- 7. Implement a solution to find the longest palindrome subsequence.
- 8. Implement a solution to find the longest palindrome substring.
- 9. Implement a solution to solve the Rod Cutting Problem.
- 10. Write a program to find the minimum cost path in a grid.
- 11. Write a program to count the number of ways to cover a distance with 1, 2, and 3 steps.
- 12. Write a program to find the optimal strategy for a game.
- 13. Write a program to solve the Egg Dropping Puzzle.
- 14. Implement a solution to find the maximum length chain of pairs.
- 15. Write a program to find the maximum sum increasing subsequence.
- 16. Write a program to solve the Matrix Chain Multiplication problem.
- 17. Write a program to find the maximum value of an expression.
- 18. Implement a solution to solve the Word Break problem.
- 19. Write a program to solve the Edit Distance problem.
- 20. Implement a solution for the Coin Change Problem.
- 21. Implement a solution for the Subset Sum Problem.
- 22. Write a program to solve the Assembly Line Scheduling problem.
- 23. Implement a solution to solve the Travelling Salesman Problem.
- 24. Write a program to solve the Longest Common Substring problem.
- 25. Write a program to find the minimum number of deletions to make a string palindrome.
- 26. Implement a solution to find the maximum sum of a subsequence with no adjacent elements.
- 27. Write a program to solve the Longest Repeated Subsequence problem.
- 28. Implement a solution to solve the Optimal Binary Search Tree problem.
- 29. Write a program to find the minimum number of jumps to reach the end of an array.
- 30. Write a program to find the maximum length of a pair chain.
- 31. Implement a solution to find the shortest common supersequence.
- 32. Write a program to solve the Box Stacking problem.
- 33. Write a program to find the minimum number of deletions to make a sequence sorted.
- 34. Implement a solution to solve the Text Justification problem.
- 35. Implement a solution to solve the Paint House problem.
- 36. Write a program to find the largest independent set in a binary tree.
- 37. Implement a solution to solve the Cutting a Rod problem.
- 38. Write a program to solve the Palindrome Partitioning problem.
- 39. Implement a solution to find the longest path in a matrix.
- 40. Write a program to solve the Optimal Game Strategy problem.
- 41. Write a program to solve the Count All Possible Paths problem.
- 42. Implement a solution to solve the Longest Arithmetic Progression problem.
- 43. Write a program to solve the Maximal Square problem.
- 44. Write a program to solve the Partition Problem.
- 45. Implement a solution to solve the Mobile Numeric Keypad problem.
- 46. Implement a solution to solve the Maximum Product Cutting problem.
- 47. Write a program to solve the Maximum Length of Pair Chain problem.
- 48. Implement a solution to find the maximum sum rectangle in a 2D matrix.
- 49. Write a program to solve the Count Number of Binary Strings without Consecutive 1’s problem.
- 50. Implement a solution to solve the Friends Pairing problem.
- MCQ Questions
- 1. What is dynamic programming?
- 2. What is memoization in dynamic programming?
- 3. What is the main advantage of using dynamic programming?
- 4. Which of the following is a necessary condition for applying dynamic programming?
- 5. What is the time complexity of a dynamic programming algorithm?
- 6. Which data structure is commonly used for memoization in dynamic programming?
- 7. What is the key idea behind the “top-down” approach in dynamic programming?
- 8. What is the key idea behind the “bottom-up” approach in dynamic programming?
- 9. What is the difference between dynamic programming and greedy algorithms?
- 10. Which of the following problems can be solved using dynamic programming?
- 11. What is the key idea behind the “optimal substructure” property in dynamic programming?
- 12. Which of the following algorithms uses dynamic programming?
- 13. What is the “state” in dynamic programming?
- 14. Which of the following is NOT a characteristic of a problem suitable for dynamic programming?
- 15. What is the purpose of the “tabulation” method in dynamic programming?
- 16. Which of the following is NOT a common application of dynamic programming?
- 17. What is the time complexity of a dynamic programming algorithm with n subproblems and each subproblem taking O(1) time?
- 18. What is the key principle of the “principle of optimality” in dynamic programming?
- 19. In dynamic programming, what is the purpose of the “recurrence relation”?
- 20. What is the principle behind the “memoryless property” of dynamic programming?
- 21. What is the main difference between top-down and bottom-up dynamic programming approaches?
- 22. What is the concept of “state space” in dynamic programming?
- 23. In dynamic programming, what is the purpose of the “optimal policy”?
- 24. Which of the following is an example of a classic dynamic programming problem?
- 25. In dynamic programming, what is the role of the “base case”?
- 26. Which of the following is an example of an optimal substructure property?
- 27. What is the purpose of the “decision space” in dynamic programming?
- 28. What is the “optimal subproblem structure” in dynamic programming?
- 29. In dynamic programming, what is the purpose of the “value function”?
- 30. What is the main advantage of using dynamic programming over other problem-solving techniques?

## 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:

```
#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):**

```
#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:**

```
#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):**

```
#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:

```
#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:**

```
#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):**

```
#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]`

.

- If the weight of the current item is less than or equal to the current capacity
- 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:**

```
#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:**

```
#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):**

```
#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):**

```
#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:**

```
#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.

- If
- Continue this process for all possible intermediate vertices.

**C++ Code for Floyd-Warshall Algorithm:**

```
#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:**

```
#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:**

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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).

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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.

```
#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;
return 0;
}
```

### 42. Implement a solution to solve the Longest Arithmetic Progression problem.

```
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int longestArithmeticProgression(vector<int>& nums) {
int n = nums.size();
if (n <= 2) {
return n;
}
int maxLen = 2;
vector<unordered_map<int,
int>> dp(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
int diff = nums[i] - nums[j];
dp[i][diff] = dp[j].count(diff) ? dp[j][diff] + 1 : 2;
maxLen = max(maxLen, dp[i][diff]);
}
}
return maxLen;
}
int main() {
vector<int> nums = {3, 6, 9, 12, 15};
int maxLen = longestArithmeticProgression(nums);
cout << "Maximum length of arithmetic progression: " << maxLen << endl;
return 0;
}
```

### 43. Write a program to solve the Maximal Square problem.

```
#include <iostream>
#include <vector>
using namespace std;
int maximalSquare(vector<vector<char>>& matrix) {
int m = matrix.size();
if (m == 0) {
return 0;
}
int n = matrix[0].size();
if (n == 0) {
return 0;
}
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
int maxSide = 0;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (matrix[i - 1][j - 1] == '1') {
dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
maxSide = max(maxSide, dp[i][j]);
}
}
}
return maxSide * maxSide;
}
int main() {
vector<vector<char>> matrix = {{'1', '0', '1', '0', '0'},
{'1', '0', '1', '1', '1'},
{'1', '1', '1', '1', '1'},
{'1', '0', '0', '1', '0'}};
int maxArea = maximalSquare(matrix);
cout << "Maximal square area: " << maxArea << endl;
return 0;
}
```

### 44. Write a program to solve the Partition Problem.

```
#include <iostream>
#include <vector>
using namespace std;
bool canPartition(vector<int>& nums) {
int n = nums.size();
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 != 0) {
return false;
}
int target = sum / 2;
vector<bool> dp(target + 1, false);
dp[0] = true;
for (int i = 0; i < n; i++) {
for (int j = target; j >= nums[i]; j--) {
dp[j] = dp[j] || dp[j - nums[i]];
}
}
return dp[target];
}
int main() {
vector<int> nums = {1, 5, 11, 5};
bool canPartitionResult = canPartition(nums);
cout << "Can partition: " << (canPartitionResult ? "true" : "false") << endl;
return 0;
}
```

### 45. Implement a solution to solve the Mobile Numeric Keypad problem.

```
#include <iostream>
#include <vector>
#include
<unordered_map>
using namespace std;
unordered_map<int, vector<int>> getAdjacentKeys() {
unordered_map<int, vector<int>> adjKeys;
adjKeys[0] = {0, 8};
adjKeys[1] = {1, 2, 4};
adjKeys[2] = {1, 2, 3, 5};
adjKeys[3] = {2, 3, 6};
adjKeys[4] = {1, 4, 5, 7};
adjKeys[5] = {2, 4, 5, 6, 8};
adjKeys[6] = {3, 5, 6, 9};
adjKeys[7] = {4, 7, 8};
adjKeys[8] = {0, 5, 7, 8, 9};
adjKeys[9] = {6, 8, 9};
return adjKeys;
}
long long countPossiblePatterns(int n) {
vector<vector<long long>> dp(10, vector<long long>(n + 1, 0));
unordered_map<int, vector<int>> adjKeys = getAdjacentKeys();
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= 9; j++) {
if (i == 1) {
dp[j][i] = 1;
continue;
}
for (int k : adjKeys[j]) {
dp[j][i] += dp[k][i - 1];
}
}
}
long long count = 0;
for (int j = 0; j <= 9; j++) {
count += dp[j][n];
}
return count;
}
int main() {
int n = 3;
long long numPatterns = countPossiblePatterns(n);
cout << "Number of possible patterns: " << numPatterns << endl;
return 0;
}
```

### 46. Implement a solution to solve the Maximum Product Cutting problem.

```
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxProductCutting(int n) {
if (n <= 1) {
return 0;
}
if (n == 2) {
return 1;
}
if (n == 3) {
return 2;
}
vector<int> dp(n + 1, 0);
dp[2] = 2;
dp[3] = 3;
for (int i = 4; i <= n; i++) {
for (int j = 1; j <= i / 2; j++) {
dp[i] = max(dp[i], dp[j] * dp[i - j]);
}
}
return dp[n];
}
int main() {
int n = 10;
int maxProduct = maxProductCutting(n);
cout << "Maximum product after cutting: " << maxProduct << endl;
return 0;
}
```

### 47. Write a program to solve the Maximum Length of Pair Chain problem.

```
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool comparePairs(const vector<int>& p1, const vector<int>& p2) {
return p1[1] < p2[1];
}
int findLongestChain(vector<vector<int>>& pairs) {
sort(pairs.begin(), pairs.end(), comparePairs);
int n = pairs.size();
int
maxChainLength = 1;
int currentEnd = pairs[0][1];
for (int i = 1; i < n; i++) {
if (pairs[i][0] > currentEnd) {
maxChainLength++;
currentEnd = pairs[i][1];
}
}
return maxChainLength;
}
int main() {
vector<vector<int>> pairs = {{1, 2}, {2, 3}, {3, 4}};
int maxChainLength = findLongestChain(pairs);
cout << "Maximum length of pair chain: " << maxChainLength << endl;
return 0;
}
```

### 48. Implement a solution to find the maximum sum rectangle in a 2D matrix.

```
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int maxSumRectangle(vector<vector<int>>& matrix) {
int rows = matrix.size();
if (rows == 0) {
return 0;
}
int cols = matrix[0].size();
if (cols == 0) {
return 0;
}
int maxSum = INT_MIN;
for (int left = 0; left < cols; left++) {
vector<int> temp(rows, 0);
for (int right = left; right < cols; right++) {
for (int i = 0; i < rows; i++) {
temp[i] += matrix[i][right];
}
int currentSum = 0;
int maxSubArraySum = INT_MIN;
for (int i = 0; i < rows; i++) {
currentSum = max(temp[i], currentSum + temp[i]);
maxSubArraySum = max(maxSubArraySum, currentSum);
}
maxSum = max(maxSum, maxSubArraySum);
}
}
return maxSum;
}
int main() {
vector<vector<int>> matrix = {{1, 2, -1, -4, -20},
{-8, -3, 4, 2, 1},
{3, 8, 10, 1, 3},
{-4, -1, 1, 7, -6}};
int maxSum = maxSumRectangle(matrix);
cout << "Maximum sum rectangle: " << maxSum << endl;
return 0;
}
```

### 49. Write a program to solve the Count Number of Binary Strings without Consecutive 1’s problem.

```
#include <iostream>
#include <vector>
using namespace std;
int countBinaryStrings(int n) {
vector<int> dp(n + 1, 0);
dp[1] = 2;
dp[2] = 3;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
int main() {
int n = 5;
int numStrings = countBinaryStrings(n);
cout << "Number of binary strings: " << numStrings << endl;
return 0;
}
```

### 50. Implement a solution to solve the Friends Pairing problem.

```
#include <iostream>
#include <vector>
using namespace std;
int countFriendPairings(int n) {
vector<int> dp(n + 1, 0);
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <=
n; i++) {
dp[i] = dp[i - 1] + (i - 1) * dp[i - 2];
}
return dp[n];
}
int main() {
int n = 4;
int numPairings = countFriendPairings(n);
cout << "Number of friend pairings: " << numPairings << endl;
return 0;
}
```

## MCQ Questions

### 1. What is dynamic programming?

a) A programming technique used to develop dynamic websites

b) A programming language used for web development

c) A problem-solving technique that uses the principles of recursion and memoization

d) A method to write efficient code using loops and conditional statements

Answer: c) A problem-solving technique that uses the principles of recursion and memoization

### 2. What is memoization in dynamic programming?

a) The process of converting a problem into smaller subproblems

b) The process of storing computed results to avoid redundant calculations

c) The process of solving a problem using iteration

d) The process of finding optimal solutions using heuristics

Answer: b) The process of storing computed results to avoid redundant calculations

### 3. What is the main advantage of using dynamic programming?

a) It guarantees the optimal solution for any problem

b) It is faster than any other problem-solving technique

c) It simplifies complex problems by breaking them into smaller subproblems

d) It eliminates the need for recursion in problem-solving

Answer: c) It simplifies complex problems by breaking them into smaller subproblems

### 4. Which of the following is a necessary condition for applying dynamic programming?

a) Overlapping subproblems

b) Independent subproblems

c) Linear subproblems

d) Non-recursive subproblems

Answer: a) Overlapping subproblems

### 5. What is the time complexity of a dynamic programming algorithm?

a) O(1)

b) O(n)

c) O(log n)

d) Depends on the specific problem and implementation

Answer: d) Depends on the specific problem and implementation

### 6. Which data structure is commonly used for memoization in dynamic programming?

a) Array

b) Linked list

c) Stack

d) Queue

Answer: a) Array

### 7. What is the key idea behind the “top-down” approach in dynamic programming?

a) Solving the problem from the bottom-up using iterative techniques

b) Breaking the problem into smaller subproblems and solving them recursively

c) Storing the results of subproblems and using them to avoid redundant calculations

d) Reversing the order of operations to improve efficiency

Answer: b) Breaking the problem into smaller subproblems and solving them recursively

### 8. What is the key idea behind the “bottom-up” approach in dynamic programming?

a) Solving the problem from the top-down using recursive techniques

b) Breaking the problem into smaller subproblems and solving them iteratively

c) Storing the results of subproblems and using them to avoid redundant calculations

d) Reversing the order of operations to improve efficiency

Answer: b) Breaking the problem into smaller subproblems and solving them iteratively

### 9. What is the difference between dynamic programming and greedy algorithms?

a) Dynamic programming guarantees the optimal solution, while greedy algorithms do not

b) Dynamic programming requires more memory than greedy algorithms

c) Dynamic programming solves problems recursively, while greedy algorithms use iteration

d) Dynamic programming is only applicable to a subset of problems, while greedy algorithms can be applied to any problem

Answer: a) Dynamic programming guarantees the optimal solution, while greedy algorithms do not

### 10. Which of the following problems can be solved using dynamic programming?

a) Sorting a list of integers in ascending order

b) Finding the maximum element in an array

c) Calculating the Fibonacci sequence

d) All of the above

Answer: c) Calculating the Fibonacci sequence

### 11. What is the key idea behind the “optimal substructure” property in dynamic programming?

a) The optimal solution to a problem can be constructed from optimal solutions to its subproblems

b) The problem can be divided into smaller subproblems that can be solved independently

c) The solution to a problem can be expressed as the combination of solutions to its subproblems

d) The problem can be solved by considering all possible choices at each step

Answer: a) The optimal solution to a problem can be constructed from optimal solutions to its subproblems

### 12. Which of the following algorithms uses dynamic programming?

a) Dijkstra’s algorithm

b) Prim’s algorithm

c) Bellman-Ford algorithm

d) All of the above

Answer: d) All of the above

### 13. What is the “state” in dynamic programming?

a) The current position in the program execution

b) The set of parameters that uniquely identifies a subproblem

c) The output produced by the program

d) The memory location where computed results are stored

Answer: b) The set of parameters that uniquely identifies a subproblem

### 14. Which of the following is NOT a characteristic of a problem suitable for dynamic programming?

a) Overlapping subproblems

b) Optimal substructure

c) Independent subproblems

d) Recursive definition

Answer: c) Independent subproblems

### 15. What is the purpose of the “tabulation” method in dynamic programming?

a) To store the results of subproblems in a table for efficient lookup

b) To divide the problem into smaller subproblems and solve them recursively

c) To apply memoization to avoid redundant calculations

d) To reorder the computations to improve efficiency

Answer: a) To store the results of subproblems in a table for efficient lookup

### 16. Which of the following is NOT a common application of dynamic programming?

a) Knapsack problem

b) Longest common subsequence

c) Graph coloring

d) Edit distance

Answer: c) Graph coloring

### 17. What is the time complexity of a dynamic programming algorithm with n subproblems and each subproblem taking O(1) time?

a) O(n)

b) O(log n)

c) O(n log n)

d) O(1)

Answer: d) O(1)

### 18. What is the key principle of the “principle of optimality” in dynamic programming?

a) Every subproblem should be solved optimally to guarantee the optimal solution for the main problem

b) Greedy choices lead to the globally optimal solution

c) The optimal solution is composed of optimal solutions to its subproblems

d) Redundant calculations should be avoided to improve efficiency

Answer: c) The optimal solution is composed of optimal solutions to its subproblems

### 19. In dynamic programming, what is the purpose of the “recurrence relation”?

a) To define the base cases of the problem

b) To determine the optimal solution to the problem

c) To express the solution to a problem in terms of solutions to smaller subproblems

d) To store computed results to avoid redundant calculations

Answer: c) To express the solution to a problem in terms of solutions to smaller subproblems

### 20. What is the principle behind the “memoryless property” of dynamic programming?

a) The current state of a problem depends only on the immediately preceding state

b) The optimal solution depends only on the current state and not on the previous states

c) The optimal solution depends only on the future states and not on the previous states

d) The current state of a problem depends only on the initial state

Answer: a) The current state of a problem depends only on the immediately preceding state

### 21. What is the main difference between top-down and bottom-up dynamic programming approaches?

a) Top-down starts from the smallest subproblem, while bottom-up starts from the largest subproblem

b) Top-down uses recursion, while bottom-up uses iteration

c) Top-down does not use memoization, while bottom-up does

d) Top-down solves the problem iteratively, while bottom-up solves it recursively

Answer: b) Top-down uses recursion, while bottom-up uses iteration

### 22. What is the concept of “state space” in dynamic programming?

a) The set of all possible subproblems in a problem

b) The set of all possible states of a dynamic programming algorithm

c) The space required to store the computed results of subproblems

d) The space required to store the input data for the problem

Answer: b) The set of all possible states of a dynamic programming algorithm

### 23. In dynamic programming, what is the purpose of the “optimal policy”?

a) To determine the optimal solution to a problem

b) To determine the sequence of decisions that leads to the optimal solution

c) To minimize the number of subproblems to be solved

d) To maximize the number of subproblems to be solved

Answer: b) To determine the sequence of decisions that leads to the optimal solution

### 24. Which of the following is an example of a classic dynamic programming problem?

a) Binary search

b) Tower of Hanoi

c) Quick sort

d) Traveling Salesman Problem

Answer: d) Traveling Salesman Problem

### 25. In dynamic programming, what is the role of the “base case”?

a) To define the smallest subproblem that can be solved directly

b) To determine the optimal solution to the problem

c) To define the state of the problem that leads to the termination of the algorithm

d) To store computed results for efficient lookup

Answer: a) To define the smallest subproblem that can be solved directly

### 26. Which of the following is an example of an optimal substructure property?

a) Bellman-Ford algorithm for finding shortest paths

b) Dijkstra’s algorithm for finding shortest paths

c) Kruskal’s algorithm for finding minimum spanning trees

d) Depth-first search algorithm for graph traversal

Answer: a) Bellman-Ford algorithm for finding shortest paths

### 27. What is the purpose of the “decision space” in dynamic programming?

a) To store the computed results of subproblems

b) To represent the set of all possible decisions or choices in a dynamic programming problem

c) To define the state of the problem

d) To determine the optimal solution to the problem

Answer: b) To represent the set of all possible decisions or choices in a dynamic programming problem

### 28. What is the “optimal subproblem structure” in dynamic programming?

a) The structure of the original problem that can be divided into smaller subproblems

b) The structure of the subproblems that allows the optimal solution to be constructed from optimal solutions to its subproblems

c) The structure of the decision space in a dynamic programming problem

d) The structure of the recurrence relation that defines the problem

Answer: b) The structure of the subproblems that allows the optimal solution to be constructed from optimal solutions to its subproblems

### 29. In dynamic programming, what is the purpose of the “value function”?

a) To represent the value or cost associated with each state or decision in a dynamic programming problem

b) To store the computed results of subproblems

c) To define the optimal policy for solving a dynamic programming problem

d) To determine the optimal solution to the problem

Answer: a) To represent the value or cost associated with each state or decision in a dynamic programming problem

### 30. What is the main advantage of using dynamic programming over other problem-solving techniques?

a) It guarantees the optimal solution for any problem

b) It is faster than any other problem-solving technique

c) It simplifies complex problems by breaking them into smaller subproblems

d) It requires less memory compared to other problem-solving techniques

Answer: c) It simplifies complex problems by breaking them into smaller subproblems