The 10 most important DP questions

Let's solve them, here is the list.

1. Longest Common Subsequence
2. Shortest Common Supersequence
3. Longest Increasing Subsequence problem
4. The Levenshtein distance (Edit distance) problem
5. Matrix Chain Multiplication
6. 0–1 Knapsack problem
7. Partition problem
8. Rod Cutting
9. Coin change problem
10. Word Break Problem

Top 10 Dynamic programming problems

1. LONGEST COMMON SUBSEQUENCE

Understanding the question:
for each letter, we will check whether this letter equals to the letter in the other string, if so we will take it, otherwise, we will continue advancing with one of the strings

// Method1()- recursive solution(Top- down approach)
    // time complexity - O(2^(m+n))
    // space complexity - O(m+n)
    public static int LCSM1(char[] X, char[] Y, int i, int j) {
        if (i <= 0 || j <= 0)
            return 0;
        if (X[i - 1] == Y[j - 1])
            return 1 + LCSM1(X, Y, i - 1, j - 1);
        else
            return Math.max(LCSM1(X, Y, i, j - 1), LCSM1(X, Y, i - 1, j));
}

we can use memoization

public static int LCSM2(char[] X, char[] Y, int i, int j, int[][] dp) {
    if (i <= 0 || j <= 0)
        return 0;

    if (dp[i][j] != 0)
        return dp[i][j];

    if (X[i - 1] == Y[j - 1])
        return 1 + LCSM2(X, Y, i - 1, j - 1, dp);
    else
        return dp[i][j] = Math.max(LCSM2(X, Y, i, j - 1, dp), LCSM2(X, Y, i - 1, j, dp));

}