// 子串必须连续
public class LongestSubstring {
    public int findLongest(String A, int n, String B, int m) {
        int dp[][] = new int[n + 1][m + 1];
        int ans = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                if (ans < dp[i][j]) {
                    ans = dp[i][j];
                }
            }
        }
        return ans;
    }
}

// 子序列不必连续
public class LongestSequence {
    public int findLCS(String A, int n, String B, int m) {
        int dp[][] = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[n][m];
    }
}

// 每次只能爬一阶或两阶，问爬上n阶有多少种方法？
class Solution {
    public int climbStairs(int n) {
        int[] dp = new int[n + 2];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

// 从矩形左上角到右下角的不同路径数
class Solution {
    public int uniquePaths(int m, int n) {
        int dp[][] = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
                }
            }
        }
        return dp[m - 1][n - 1];
    }
}

// 字符串A经过插入，删除，修改三种操作变为字符串B的步骤数
class Solution {
    public int minDistance(String word1, String word2) {
        if (word1.equals(word2)) {
            return 0;
        }
        if (word1.length() == 0 || word2.length() == 0) {
            return Math.max(word1.length(), word2.length());
        }
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        int i, j;
        // 初始化，有一个单词长度为0时，则需要采取进行另一个单词的长度次操作
        for (i = 0; i <= word1.length(); i++) {
            dp[i][0] = i;
        }
        for (j = 0; j <= word2.length(); j++) {
            dp[0][j] = j;
        }
        for (i = 1; i <= word1.length(); i++) {
            for (j = 1; j <= word2.length(); j++) {
                // 刚好word1[i] == word2[j]时，下标从0开始，但是dp数组从1开始，dp[0][0]表示空串
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
                    // 如果不等，可以通过修改或者删除最后一个字符，增加一次操作
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }
}

public class GetMoney {
    public int countWays(int[] changes, int n, int x) {
        //抄袭的代码
        int[] dp = new int[x + 1];
        dp[0] = 1;
        for (int change : changes) {
            for (int i = 0; i + change <= x; i++) {
                dp[i + change] += dp[i];
            }
        }
        return dp[x];
    }
}