动态规划：从入门到精通

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    int ans = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        ans = Math.max(ans, dp[i]);
    }
    return ans;
}

public int longestCommonSubsequence(String s1, String s2) {
    int m = s1.length(), n = s2.length();
    int[][] dp = new int[m + 1][n + 1];   // dp[i][j] = s1[0..i) 与 s2[0..j) 的 LCS 长度
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[m][n];
}

// n 件物品，weights[i] 重量，values[i] 价值，容量 W
public int knapsack01(int[] weights, int[] values, int W) {
    int n = weights.length;
    int[] dp = new int[W + 1];                       // 滚动数组
    for (int i = 0; i < n; i++) {
        for (int j = W; j >= weights[i]; j--) {     // ⚠️ 倒序：避免重复选
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

public int knapsackComplete(int[] weights, int[] values, int W) {
    int n = weights.length;
    int[] dp = new int[W + 1];
    for (int i = 0; i < n; i++) {
        for (int j = weights[i]; j <= W; j++) {     // ✅ 正序：允许重复
            dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[W];
}

for (int len = 2; len <= n; len++) {           // 区间长度
    for (int l = 0; l + len - 1 < n; l++) {
        int r = l + len - 1;
        dp[l][r] = Integer.MAX_VALUE;
        for (int k = l; k < r; k++) {           // 分割点
            dp[l][r] = Math.min(dp[l][r], dp[l][k] + dp[k+1][r] + cost(l, r, k));
        }
    }
}

public int longestPalindromeSubseq(String s) {
    int n = s.length();
    int[][] dp = new int[n][n];
    for (int i = 0; i < n; i++) dp[i][i] = 1;
    for (int len = 2; len <= n; len++) {
        for (int l = 0; l + len - 1 < n; l++) {
            int r = l + len - 1;
            if (s.charAt(l) == s.charAt(r)) {
                dp[l][r] = dp[l + 1][r - 1] + 2;
            } else {
                dp[l][r] = Math.max(dp[l + 1][r], dp[l][r - 1]);
            }
        }
    }
    return dp[0][n - 1];
}

// dp[i][0]=持有，dp[i][1]=不持有且在冷冻期，dp[i][2]=不持有且不在冷冻期
dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i]);
dp[i][1] = dp[i-1][0] + prices[i];
dp[i][2] = max(dp[i-1][1], dp[i-1][2]);

int[] dfs(TreeNode u) {
    int[] res = new int[2];    // res[0]=不选u, res[1]=选u
    if (u == null) return res;
    int[] l = dfs(u.left), r = dfs(u.right);
    res[0] = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);
    res[1] = u.val + l[0] + r[0];
    return res;
}

public int minDistance(String word1, String word2) {
    int m = word1.length(), n = word2.length();
    int[][] dp = new int[m + 1][n + 1];
    for (int i = 0; i <= m; i++) dp[i][0] = i;     // 删除 i 次
    for (int j = 0; j <= n; j++) dp[0][j] = j;     // 插入 j 次
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1];        // 不需操作
            } else {
                dp[i][j] = 1 + Math.min(
                    dp[i - 1][j],                    // 删除 word1[i-1]
                    Math.min(dp[i][j - 1],           // 插入 word2[j-1]
                             dp[i - 1][j - 1])       // 替换
                );
            }
        }
    }
    return dp[m][n];
}

long dfs(int pos, boolean tight, boolean lead, int... other) {
    if (pos == -1) return (lead ? 0 : 1);  // 取决于定义
    if (!tight && !lead && memo[pos][...] != -1) return memo[pos][...];
    long ans = 0;
    int up = tight ? digits[pos] : 9;
    for (int d = 0; d <= up; d++) {
        ans += dfs(pos - 1, tight && d == up, lead && d == 0, ...);
    }
    if (!tight && !lead) memo[pos][...] = ans;
    return ans;
}