DEV Community

Cover image for Dynamic Programming, Coding Interview Pattern
Harsh Mishra
Harsh Mishra

Posted on

Dynamic Programming, Coding Interview Pattern

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

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];
    }
};
Enter fullscreen mode Exit fullscreen mode

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

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];
    }
};
Enter fullscreen mode Exit fullscreen mode

Coin Change

This question is part of Leetcode problems, question no. 322.

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

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];
    }
};
Enter fullscreen mode Exit fullscreen mode

Rod Cutting Problem

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

#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];
    }
};
Enter fullscreen mode Exit fullscreen mode

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

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];
    }
};
Enter fullscreen mode Exit fullscreen mode

Climbing Stairs

This question is part of Leetcode problems, question no. 70.

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

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];
    }
};
Enter fullscreen mode Exit fullscreen mode

House Robber

This question is part of Leetcode problems, question no. 198.

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

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];
    }
};
Enter fullscreen mode Exit fullscreen mode

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

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];
    }
};
Enter fullscreen mode Exit fullscreen mode

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

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;
    }
};
Enter fullscreen mode Exit fullscreen mode

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

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];
    }
};
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)