Dynamic Programming, Coding Interview Pattern
Tags: coding, interview, algorithms, dsa
Published: 2024-06-24 09:29:21

## Dynamic Programming

Dynamic Programming (DP) is a powerful algorithmic technique used to solve optimization problems by breaking them down into simpler subproblems and storing the solutions to those subproblems to avoid redundant computations. It is particularly useful for problems where the solution can be recursively defined in terms of solutions to overlapping subproblems. By efficiently storing and reusing intermediate results, DP can drastically improve the efficiency of algorithms that would otherwise be computationally expensive. This guide explores the foundational concepts of Dynamic Programming, its key components like memoization and tabulation, and provides insights into applying DP to various problem types, ranging from sequence alignment and shortest path calculations to resource allocation and scheduling problems.

### 0/1 Knapsack Problem
`This problem is a classic dynamic programming problem.`

Here's the Solution class for the "0/1 Knapsack Problem" in C++:

```cpp
class Solution {
public:
    int knapsack(int W, vector<int>& weights, vector<int>& values) {
        int n = weights.size();
        vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
        
        for (int i = 1; i <= n; ++i) {
            for (int w = 0; w <= W; ++w) {
                if (weights[i - 1] <= w) {
                    dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);
                } else {
                    dp[i][w] = dp[i - 1][w];
                }
            }
        }
        
        return dp[n][W];
    }
};
```

### Subset Sum
`This problem is a variation of the 0/1 knapsack problem.`

Here's the Solution class for the "Subset Sum" problem in C++:

```cpp
class Solution {
public:
    bool subsetSum(vector<int>& nums, int S) {
        int n = nums.size();
        vector<vector<bool>> dp(n + 1, vector<bool>(S + 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 <= S; ++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][S];
    }
};
```

### Coin Change
`This question is part of Leetcode problems, question no. 322.`

Here's the Solution class for the "Coin Change" problem in C++:

```cpp
class Solution {
public:
    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 coin : coins) {
                if (coin <= i) {
                    dp[i] = min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        
        return dp[amount] > amount ? -1 : dp[amount];
    }
};
```

### Rod Cutting Problem

Here's the Solution class for the "Rod Cutting Problem" in C++:

```cpp
#include <vector>
#include <algorithm>
#include <climits>

class Solution {
public:
    int rodCutting(int length, vector<int>& prices) {
        vector<int> dp(length + 1, 0);
        
        for (int i = 1; i <= length; ++i) {
            int maxProfit = INT_MIN;
            for (int j = 1; j <= i; ++j) {
                maxProfit = max(maxProfit, prices[j - 1] + dp[i - j]);
            }
            dp[i] = maxProfit;
        }
        
        return dp[length];
    }
};
```

### Nth Tribonacci Number
`This question is part of Leetcode problems, question no. 1137.`

Here's the Solution class for the "Nth Tribonacci Number" problem in C++:

```cpp
class Solution {
public:
    int tribonacci(int n) {
        if (n == 0) return 0;
        if (n == 1 || n == 2) return 1;
        
        int dp[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        
        for (int i = 3; i <= n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        
        return dp[n];
    }
};
```

### Climbing Stairs
`This question is part of Leetcode problems, question no. 70.`

Here's the Solution class for the "Climbing Stairs" problem in C++:

```cpp
class Solution {
public:
    int climbStairs(int n) {
        if (n == 0 || n == 1) return 1;
        
        vector<int> dp(n + 1, 0);
        dp[0] = 1;
        dp[1] = 1;
        
        for (int i = 2; i <= n; ++i) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        
        return dp[n];
    }
};
```

### House Robber
`This question is part of Leetcode problems, question no. 198.`

Here's the Solution class for the "House Robber" problem in C++:

```cpp
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        
        vector<int> dp(n, 0);
        dp[0] = nums[0];
        dp[1] = max(nums[0], nums[1]);
        
        for (int i = 2; i < n; ++i) {
            dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        
        return dp[n - 1];
    }
};
```

### Longest Common Subsequence
`This question is part of Leetcode problems, question no. 1143.`

Here's the Solution class for the "Longest Common Subsequence" problem in C++:

```cpp
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        int m = text1.size();
        int n = text2.size();
        
        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] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        
        return dp[m][n];
    }
};
```

### Longest Increasing Subsequence
`This question is part of Leetcode problems, question no. 300.`

Here's the Solution class for the "Longest Increasing Subsequence" problem in C++:

```cpp
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0;
        
        vector<int> dp(n, 1);
        int maxLength = 1;
        
        for (int i = 1; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (nums[j] < nums[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            maxLength = max(maxLength, dp[i]);
        }
        
        return maxLength;
    }
};
```

### Equal Subset Sum Partition
`This question is part of Leetcode problems, question no. 416.`

Here's the Solution class for the "Equal Subset Sum Partition" problem in C++:

```cpp
class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int totalSum = accumulate(nums.begin(), nums.end(), 0);
        
        if (totalSum % 2 != 0) {
            return false;
        }
        
        int target = totalSum / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true;
        
        for (int num : nums) {
            for (int j = target; j >= num; --j) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        
        return dp[target];
    }
};
```

Practice these questions diligently to enhance your problem-solving skills. Remember, consistent practice is key to mastering these concepts. If you find yourself stuck or in need of further clarification, be sure to check out video references and tutorials to clear up any doubts.