输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

class Solution {
    /**
     * 70. 爬楼梯（暴力递归）
     *
     * @param n 	楼梯阶数
     * @return 		方案总数
     */
    public int climbStairs(int n) {
        if (n == 0) return 1;
        if (n < 0) return 0;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
}

class Solution {
    /**
     * 70. 爬楼梯（记忆化）
     *
     * @param n 	楼梯阶数
     * @return 		方案总数
     */
    public int climbStairs(int n) {
        int[] memo = new int[n + 1];
        return helper(n, memo);
    }
    
    private int helper(int n, int[] memo) {
        if (n == 0) return 1;
        if (n < 0) return 0;
        if (memo[n] != 0) return memo[n];  // 避免重复计算
        
        memo[n] = helper(n - 1, memo) + helper(n - 2, memo);
        return memo[n];
    }
}

class Solution {
    /**
     * 70. 爬楼梯（标准dp）
     *
     * @param n 	楼梯阶数
     * @return 		方案总数
     */
    public int climbStairs(int n) {
        if (n <= 2) return n;
        
        int[] dp = new int[n + 1];
        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 {
    /**
     * 70. 爬楼梯（滚动数组）
     *
     * @param n 	楼梯阶数
     * @return 		方案总数
     */
    public int climbStairs(int n) {
        if (n <= 2) return n;
        
        // 只需要3个变量：prev2, prev1, current
        int prev2 = 1;  // dp[i-2]
        int prev1 = 2;  // dp[i-1]
        int current = 0;
        
        for (int i = 3; i <= n; i++) {
            current = prev1 + prev2;  // 状态转移
            prev2 = prev1;  // 滚动更新
            prev1 = current;
        }
        
        return current;
    }
}

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

输入: numRows = 1
输出: [[1]]

    /**
     * 118. 杨辉三角（dp）
     *
     * @param n 	层数
     * @return 		杨辉三角系数
     */
	public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>();
        
        // 第一行
        ans.add(new ArrayList<>(Arrays.asList(1)));
        if (numRows == 1) return ans;
        
        // 第二行
        ans.add(new ArrayList<>(Arrays.asList(1, 1)));
        if (numRows == 2) return ans;
        
        // 初始状态
        int[][] dp = new int[numRows + 1][];
        dp[2] = new int[]{1, 1};
        
        for (int i = 3; i <= numRows; i++) {
            // 每一行的第一个设为1
            List<Integer> temp = new ArrayList<>();
            dp[i] = new int[numRows];
            dp[i][0] = 1;
            temp.add(dp[i][0]);

            for (int j = 1; j < i - 1; j++) {
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
                temp.add(dp[i][j]);
            }
            
            // 每一行的最后一个设为1
            dp[i][i - 1] = 1;
            temp.add(dp[i][i - 1]);

            ans.add(temp);
        }
        return ans;
    }

    /**
     * 118. 杨辉三角（优化dp）
     *
     * @param n 	层数
     * @return 		杨辉三角系数
     */
	public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>();
        
        for (int i = 0; i < numRows; i++) {
            List<Integer> row = new ArrayList<>();
            
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    int left = ans.get(i - 1).get(j - 1);
                    int right = ans.get(i - 1).get(j);
                    row.add(left + right);
                }
            }
            
            ans.add(row);
        }
        
        return ans;
    }

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

class Solution {
    /**
     * 198. 打家劫舍（dp）
     *
     * @param nums 	每家金额
     * @return 		最大金额
     */
    public int rob(int[] nums) {
        int length = nums.length;
        if (length == 1) return nums[0];
        int[] dp = new int[length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);

        for (int i = 2; i < length; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[length - 1];
    }
}

class Solution {
    /**
     * 198. 打家劫舍（优化dp）
     *
     * @param nums 	每家金额
     * @return 		最大金额
     */
    public int rob(int[] nums) {
        int length = nums.length;
        if (length == 1) return nums[0];
        int dp0 = nums[0], dp1 = Math.max(nums[0], nums[1]);

        for (int i = 2; i < length; i++) {
            int temp = dp1;		// 记录旧的dp1
            dp1 = Math.max(dp0 + nums[i], dp1);	// 更新dp1
            dp0 = temp;			// 把dp1赋给dp0
        }
        return dp1;
    }
}

输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

输入：n = 13
输出：2
解释：13 = 4 + 9

class Solution {
    /**
     * 279. 完全平方数（dp）
     *
     * @param n 	目标数
     * @return 		最少平方数
     */
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        
        // 初始化dp数组
        for (int i = 0; i <= n; i++) {
            dp[i] = i;  // 最坏情况：全用1
        }
        
        // 遍历完全平方数
        for (int i = 2; i * i <= n; i++) {
            int square = i * i;
            
            // 更新dp数组
            for (int j = square; j <= n; j++) {
                dp[j] = Math.min(dp[j], dp[j - square] + 1);
            }
        }
        
        return dp[n];
    }
}

dp[0] = 0
dp[1] = 1
dp[2] = 2
dp[3] = 3
dp[4] = 4
dp[5] = 5
dp[6] = 6
dp[7] = 7
dp[8] = 8
dp[9] = 9
dp[10] = 10
dp[11] = 11
dp[12] = 12

j=4:
dp[4] = Math.min(dp[4]=4, dp[4-4]=dp[0]=0 + 1=1) = 1
dp数组变为：dp[4]=1

j=5:
dp[5] = Math.min(dp[5]=5, dp[5-4]=dp[1]=1 + 1=2) = 2
dp数组变为：dp[5]=2

j=6:
dp[6] = Math.min(dp[6]=6, dp[6-4]=dp[2]=2 + 1=3) = 3
dp数组变为：dp[6]=3

j=7:
dp[7] = Math.min(dp[7]=7, dp[7-4]=dp[3]=3 + 1=4) = 4
dp数组变为：dp[7]=4

j=8:
dp[8] = Math.min(dp[8]=8, dp[8-4]=dp[4]=1 + 1=2) = 2  // 这里dp[4]已经是1了
dp数组变为：dp[8]=2

j=9:
dp[9] = Math.min(dp[9]=9, dp[9-4]=dp[5]=2 + 1=3) = 3
dp数组变为：dp[9]=3

j=10:
dp[10] = Math.min(dp[10]=10, dp[10-4]=dp[6]=3 + 1=4) = 4
dp数组变为：dp[10]=4

j=11:
dp[11] = Math.min(dp[11]=11, dp[11-4]=dp[7]=4 + 1=5) = 5
dp数组变为：dp[11]=5

j=12:
dp[12] = Math.min(dp[12]=12, dp[12-4]=dp[8]=2 + 1=3) = 3
dp数组变为：dp[12]=3

j=9:
dp[9] = Math.min(dp[9]=3, dp[9-9]=dp[0]=0 + 1=1) = 1
dp数组变为：dp[9]=1

j=10:
dp[10] = Math.min(dp[10]=4, dp[10-9]=dp[1]=1 + 1=2) = 2
dp数组变为：dp[10]=2

j=11:
dp[11] = Math.min(dp[11]=5, dp[11-9]=dp[2]=2 + 1=3) = 3
dp数组变为：dp[11]=3

j=12:
dp[12] = Math.min(dp[12]=3, dp[12-9]=dp[3]=3 + 1=4) = 3
// 因为3 < 4
dp数组保持：dp[12]=3

class Solution {
    public int numSquares(int n) {
        // 定理：任何正整数可以表示为4个整数的平方和
        
        // 1. 检查是否是完全平方数
        if (isSquare(n)) return 1;
        
        // 2. 检查是否是两个平方数之和
        for (int i = 1; i * i <= n; i++) {
            if (isSquare(n - i * i)) return 2;
        }
        
        // 3. 根据勒让德三平方和定理
        // n != 4^k*(8m+7) 时，可以是3个平方数
        while (n % 4 == 0) {
            n /= 4;
        }
        if (n % 8 == 7) return 4;
        
        // 4. 其他情况为3
        return 3;
    }
    
    private boolean isSquare(int n) {
        int sqrt = (int) Math.sqrt(n);
        return sqrt * sqrt == n;
    }
}

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

输入：coins = [2], amount = 3
输出：-1

输入：coins = [1], amount = 0
输出：0

class Solution {
    /**
     * 322. 零钱兑换（dp）
     *
     * @param coins 	硬币面值数组
     * @param amount 	目标金额     
     * @return 			最少金币数
     */
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;

        for (int i = 0; i < coins.length; i++) {
            for (int j = coins[i]; j <= amount; j++) {
                dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
            }
        }
        return dp[amount] < amount + 1 ? dp[amount] : -1;
    }
}

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

class Solution {
    /**
     * 139. 单词拆分（记忆化）
     *
     * @param s 		目标字符串
     * @param wordDict 	字典     
     * @return 			字典中的单词能否拼接成目标字符串
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> words = new HashSet<>(wordDict);
        return dfs(s, words, 0, new Boolean[s.length()]);
    }

    private boolean dfs(String s, Set<String> words, int start, Boolean[] memo) {
        int length = s.length();
        // 如果递归到了尽头，说明可以分割
        if (start == length) return true;
        if (memo[start] != null) return memo[start];

        for (int end = start + 1; end <= length; end++) {
            String word = s.substring(start, end);

            // 如果字典中包含该子串
            if (words.contains(word)) {
                // 以当前终点为新的起点递归
                if (dfs(s, words, end, memo)) {
                    memo[start] = true;
                    return true;
                }
            }
        }
        memo[start] = false;
        return false;
    }
}

class Solution {
    /**
     * 139. 单词拆分（dp）
     *
     * @param s 		目标字符串
     * @param wordDict 	字典     
     * @return 			字典中的单词能否拼接成目标字符串
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        Set<String> words = new HashSet<>(wordDict);
        int length = s.length();
        boolean[] dp = new boolean[length + 1];
        dp[0] = true;   // 首字母是合法分割起点

        for (int i = 0; i <= length; i++) {
            // 判断是否为合法分割起点
            if (!dp[i]) continue;
            for (int j = i + 1; j <= length; j++) {
                String word = s.substring(i, j);
                // 如果字典中包含该子串
                if (words.contains(word)) {
                    dp[j] = dp[i];
                }
            }
        }
        return dp[length];
    }
}

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

输入：nums = [0,1,0,3,2,3]
输出：4

输入：nums = [7,7,7,7,7,7,7]
输出：1

class Solution {
    /**
     * 300. 最长递增子序列（dp，枚举起点）
     *
     * @param nums 		原始数组
     * @return 			最长严格递增子序列的长度
     */
    public int lengthOfLIS(int[] nums) {
        int length = nums.length;
        int[] dp = new int[length];
        int ans = 1;
        Arrays.fill(dp, 1);
        for (int i = 0; i < length; i++) {
            // 如果即使把后面所有位置都接上，长度也不可能超过 ans，就跳过 i
            if (dp[i] + (length - i - 1) <= ans) continue;

            for (int j = i + 1; j < length; j++) {
                if (nums[i] < nums[j]) {
                    dp[j] = Math.max(dp[j], dp[i] + 1);
                    ans = Math.max(ans, dp[j]);
                }
            }
        }
        return ans;
    }
}

class Solution {
    /**
     * 300. 最长递增子序列（dp，枚举终点）
     *
     * @param nums 		原始数组
     * @return 			最长严格递增子序列的长度
     */
    public int lengthOfLIS(int[] nums) {
        int length = nums.length;
        int[] dp = new int[length];
        int ans = 1;
        Arrays.fill(dp, 1);
        for (int i = 0; i < length; 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;
    }
}

class Solution {
    /**
     * 300. 最长递增子序列（贪心 + 二分查找）
     *
     * @param nums 		原始数组
     * @return 			最长严格递增子序列的长度
     */
    public int lengthOfLIS(int[] nums) {
        int length = nums.length;
        List<Integer> greedy = new ArrayList<>();
        for (int n : nums) {
            int l = 0, r = greedy.size();
            while (l < r) {
                int m = (l + r) >> 1;
                if (n > greedy.get(m)) l = m + 1;   // 如果当前元素比中点元素还要大
                else r = m;
            }
            if (l == greedy.size()) greedy.add(n);
            else greedy.set(l, n);
        }
        return greedy.size();
    }
}

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

class Solution {
    /**
     * 152. 乘积最大子数组（dp，枚举终点）
     *
     * @param nums 		原始数组
     * @return 			最大子序列乘积
     */
    public int maxProduct(int[] nums) {
        int length = nums.length;
        int min = nums[0], max = nums[0], ans = nums[0];

        for (int i = 1; i < length; i++) {
            if (nums[i] < 0) {	// 如果当前元素 < 0，由于|nums[i]| >= 1，故交换最大最小值
                int temp = min;
                min = max;
                max = temp;
            }
            max = Math.max(nums[i] * max, nums[i]);		// 累计计数或者重新计数
            min = Math.min(nums[i] * min, nums[i]);
            ans = Math.max(ans, max);
        }

        return ans;
    }
}

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

class Solution {
    /**
     * 416. 分割等和子集（dp）
     *
     * @param nums 		原始数组
     * @return 			最大子序列乘积
     */
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int n : nums) sum += n;
        if (sum % 2 != 0) return false;

        sum = sum >> 1;
        int length = nums.length;
        boolean[] dp = new boolean[sum + 1];
        dp[0] = true;

        for (int n : nums) {
            for (int j = sum; j >= n; j--) {
                dp[j] = dp[j] || dp[j - n];
            }
            if (dp[sum]) return true;
        }
        
        return false;
    }
}

输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"

输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"

输入：s = ""
输出：0

class Solution {
    /**
     * 32. 最长有效括号（栈，暴力）
     *
     * @param s 括号字符串
     * @return 最长有效长度
     */
    public int longestValidParentheses(String s) {
        int length = s.length();
        boolean[] arr = new boolean[length];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < length; i++) {
            if (s.charAt(i) == '(') stack.push(i);
            else if (!stack.isEmpty()) {
                arr[i] = true;
                arr[stack.pop()] = true;
            }
        }

        int ans = 0;
        for (int i = 0; i < length;) {
            int temp = 0;
            while (i < length && arr[i++]) temp++;
            ans = Math.max(ans, temp);
        }

        return ans;
    }
}

class Solution {
    /**
     * 32. 最长有效括号（栈，单次遍历）
     *
     * @param s 括号字符串
     * @return 最长有效长度
     */
    public int longestValidParentheses(String s) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(-1); // 哨兵：上一个不匹配位置
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i); // 当前 ) 不匹配，更新基准
                } else {
                    ans = Math.max(ans, i - stack.peek()); // 以 i 结尾的有效长度
                }
            }
        }
        return ans;
    }
}

s  = ( ( ) ( ) ( ) ( ( )
dp = 0 0 2 0 4 0 6 0 0 2
当 s[i] = ')' 且 s[i-1] = '(' 时：
dp[i] = dp[i-2] + 2
 ↑           ↑
 当前长度    前前位置的有效长度

s  = ( ( ) ( ) ( ) ) ( ( ) )
dp = 0 0 2 0 4 0 6 8 0 0 2 12
当 s[i] = ')' 且 s[i-1] = ')' 时：
需要找到与当前 ')' 匹配的 '('
匹配位置 = i - dp[i-1] - 1

👆举例：当前位置：i=11, s[11]=')'
前一个：i-1=10, s[10]=')', dp[10]=2
匹配位置：11-2-1=8, s[8]='('
计算：dp[11] = 2 + 2 + dp[7] = 4 + 8 = 12
对应整个字符串："(()()())(())"（索引0-11，长度12）

如果 s[匹配位置] = '('，则：
dp[i] = dp[i-1] + 2 + dp[匹配位置-1]
          ↑       ↑       ↑
       内部长度  当前匹配  前面有效长度

class Solution {
    /**
     * 32. 最长有效括号（dp）
     *
     * @param s 括号字符串
     * @return 最长有效长度
     */
    public int longestValidParentheses(String s) {
        int length = s.length();
        int ans = 0;
        int[] dp = new int[length + 2];
        
        for (int i = 0; i < length; i++) {
            if (s.charAt(i) == ')') {
                // 匹配 "()"
                if (i > 0 && s.charAt(i - 1) == '(') {
                    dp[i + 2] = dp[i] + 2;
                } 
                // 匹配 "))"
                else if (i > 0 && s.charAt(i - 1) == ')') {
                    int prevLen = dp[i + 1];  // 前一个有效长度
                    if (prevLen > 0 && i - prevLen - 1 >= 0 && s.charAt(i - prevLen - 1) == '(') {
                        dp[i + 2] = prevLen + 2 + dp[i - prevLen];
                    }
                }
                ans = Math.max(ans, dp[i + 2]);
            }
        }
        
        return ans;
    }
}

输入：m = 3, n = 7
输出：28

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

输入：m = 7, n = 3
输出：28

输入：m = 3, n = 3
输出：6

class Solution {
    /**
     * 62. 不同路径（数学解法，但溢出）
     *
     * @param m 	网格图的长
     * @param n 	网格图的宽   
     * @return 		路径总数
     */
    public int uniquePaths(int m, int n) {
        return factorial(n + m - 2) / factorial(m - 1) / factorial(n - 1); 
    }

    private int factorial(int x) {
        if (x == 0) return 1;
        return x * factorial(x - 1);
    }
}

class Solution {
    /**
     * 62. 不同路径（数学解法）
     *
     * @param m 	网格图的长
     * @param n 	网格图的宽   
     * @return 		路径总数
     */
    public int uniquePaths(int m, int n) {
        return (int) chooseSum(m - 1, n - 1);
    }

    private long chooseSum(int a, int b) {
        if (a < 0 || b < 0) return -1;
        int n = a + b;
        int k = Math.min(a, b);
        long res = 1;
        for (int i = 1; i <= k; i++) {
            res = res * (n - k + i) / i;	// 一定能整除
        }
        return res;
    }
}

class Solution {
    /**
     * 62. 不同路径（dp）
     *
     * @param m 	网格图的长
     * @param n 	网格图的宽   
     * @return 		路径总数
     */
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        dp[1][0] = 1;
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        }
        
        return dp[m][n];
    }
}

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

输入：grid = [[1,2,3],[4,5,6]]
输出：12

class Solution {
    /**
     * 64. 最小路径和（dp）
     *
     * @param grid 	路径权值二维数组
     * @return 		路径权值最小和
     */
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] dp = new int[m + 1][n + 1];
        
        for (int i = 0; i <= m; i++) dp[i][0] = Integer.MAX_VALUE;
        for (int i = 0; i <= n; i++) dp[0][i] = Integer.MAX_VALUE;
        dp[1][0] = 0;  
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        
        return dp[m][n];
    }
}

class Solution {
    /**
     * 64. 最小路径和（dp，无额外空间）
     *
     * @param grid 	路径权值二维数组
     * @return 		路径权值最小和
     */
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;

        for (int j = 1; j < n; j++) {
            grid[0][j] += grid[0][j - 1];
        }
        
        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i - 1][0];
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        
        return grid[m - 1][n - 1];
    }
}

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

输入：s = "cbbd"
输出："bb"

    /**
     * 131. 分割回文串（dp + 回溯）
     *
     * @param s 要分割的字符串
     * @return 所有分割完且是回文串的集合
     */
...
		// DP预处理：计算所有子串是否是回文
        for (int j = 0; j < n; j++) {
            for (int i = 0; i <= j; i++) {
                if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                }
            }
        }
...

class Solution {
    /**
     * 5. 最长回文子串（dp）
     *
     * @param grid 	路径权值二维数组
     * @return 		路径权值最小和
     */
    public String longestPalindrome(String s) {
        int length = s.length();

        boolean[][] dp = new boolean[length][length];
        int start = 0, maxLen = 1;
        
        for (int j = 0; j < length; j++) {
            dp[j][j] = true;  // 单个字符
            
            for (int i = 0; i < j; i++) {
                if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    
                    if (j - i + 1 > maxLen) {
                        maxLen = j - i + 1;
                        start = i;
                    }
                }
            }
        }
        
        return s.substring(start, start + maxLen);
    }
}

class Solution {
    /**
     * 5. 最长回文子串（中心扩展）
     *
     * @param grid 	路径权值二维数组
     * @return 		路径权值最小和
     */
    public String longestPalindrome(String s) {        
        int start = 0, end = 0;
        
        for (int i = 0; i < s.length(); i++) {
            // 以单个字符为中心
            int len1 = expand(s, i, i);
            // 以两个字符为中心  
            int len2 = expand(s, i, i + 1);
            
            int len = Math.max(len1, len2);
            if (len > end - start) {
                start = i - (len - 1) / 2;
                end = i + len / 2;
            }
        }
        
        return s.substring(start, end + 1);
    }
    
    private int expand(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
            left--;
            right++;
        }
        return right - left - 1;  // 回文长度
    }
}

输入：text1 = "abcde", text2 = "ace" 
输出：3  
解释：最长公共子序列是 "ace" ，它的长度为 3 。

输入：text1 = "abc", text2 = "abc"
输出：3
解释：最长公共子序列是 "abc" ，它的长度为 3 。

输入：text1 = "abc", text2 = "def"
输出：0
解释：两个字符串没有公共子序列，返回 0 。

class Solution {
    /**
     * 1143. 最长公共子序列（二维dp）
     *
     * @param text1 	字符串1
     * @param text2 	字符串2
     * @return 			最长公共子序列
     */
    public int longestCommonSubsequence(String text1, String text2) {
        int length1 = text1.length(), length2 = text2.length();
        int[][] dp = new int[length1 + 1][length2 + 1];

        for (int i = 1; i <= length1; i++) {
            char cur = text1.charAt(i - 1);
            for (int j = 1; j <= length2; j++) {
                if (cur == text2.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[length1][length2];
    }
}

class Solution {
    /**
     * 1143. 最长公共子序列（一维dp）
     *
     * @param text1 	字符串1
     * @param text2 	字符串2
     * @return 			最长公共子序列
     */
    public int longestCommonSubsequence(String text1, String text2) {
        if (text1.length() > text2.length()) return longestCommonSubsequence(text2, text1);
        int length1 = text1.length(), length2 = text2.length();
        int[] dp = new int[length2 + 1];
        int max = 0;

        for (int i = 1; i <= length1; i++) {
            char cur = text1.charAt(i - 1);
            int memo = 0;
            for (int j = 1; j <= length2; j++) {
                int origin = dp[j];	// 记录的dp[j]对于下次循环来说就是未更新的dp[j-1]

                if (cur == text2.charAt(j - 1)) {
                    dp[j] = memo + 1;
                } else dp[j] = Math.max(dp[j], dp[j - 1]);

                memo = origin;
            }
        }


        return dp[length2];
    }
}

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

输入：word1 = "intention", word2 = "execution"
输出：5
解释：
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

class Solution {
    /**
     * 72. 编辑距离（LCS错误解答）
     *
     * @param word1 	源单词
     * @param word2 	目标单词
     * @return 			最小编辑距离
     */
    public int minDistance(String word1, String word2) {
        int length1 = word1.length(), length2 = word2.length();
        int[][] dp = new int[length1 + 1][length2 + 1];

        for (int i = 1; i <= length1; i++) {
            char cur = word1.charAt(i - 1);
            for (int j = 1; j <= length2; j++) {
                if (cur == word2.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]);
            }
        }

        int same = dp[length1][length2];    // 已经相同的字母个数
        if (same == length2) return length1 - length2;

        int diff = length2 - same;      // word2中还差几个字母

        return diff + Math.abs(length1 - length2);  // 多则删，少则加
    }
}

// 输入，最长公共子序列为os，长度2，（3-2）+（5-3）= 3，正确
word1 = "horse"
word2 = "ros"

// 输出
3
// 预期结果
3

// 输入，最长公共子序列为etion，长度5，（9-5）+（9-9）= 4
word1 = "intention"
word2 = "execution"

// 输出
4
// 预期结果
5

word1 = "int n    "
word2 = "ex cu    "

class Solution {
    /**
     * 72. 编辑距离（二维dp）
     *
     * @param word1 	源单词
     * @param word2 	目标单词
     * @return 			最小编辑距离
     */
    public int minDistance(String word1, String word2) {
        int length1 = word1.length(), length2 = word2.length();
        int[][] dp = new int[length1 + 1][length2 + 1];     // word1前i个转换成word2前j个字符相同最少次数

        for (int i = 1; i <= length2; i++) dp[0][i] = i;       

        for (int i = 1; i <= length1; i++) {
            dp[i][0] = i;
            for (int j = 1; j <= length2; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
                else dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
            }
        }
        return dp[length1][length2];
    }
}

class Solution {
    /**
     * 72. 编辑距离（一维dp）
     *
     * @param word1 	源单词
     * @param word2 	目标单词
     * @return 			最小编辑距离
     */
    public int minDistance(String word1, String word2) {
        int length1 = word1.length(), length2 = word2.length();
        int[] dp = new int[length2 + 1];     // 转换成word2前j个字符最少次数
        for (int i = 1; i <= length2; i++) dp[i] = i;

        for (int i = 1; i <= length1; i++) {
            int memo = dp[0];
            dp[0] = i;
            char cur = word1.charAt(i - 1);
        
            for (int j = 1; j <= length2; j++) {
                int origin = dp[j];
                if (cur == word2.charAt(j - 1)) dp[j] = memo;
                else dp[j] = Math.min(Math.min(memo, origin), dp[j - 1]) + 1;
                memo = origin;
            }
        }

        return dp[length2];
    }
}