class Solution {
    public int fib(int n) {
        if (n < 2) return n;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i < n + 1; i ++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
}

// 分割等和子集，就是01背包，选n个值出来成一堆，使得两堆和相同
class Solution {
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) return false;
        int mid = sum / 2;
        int[] dp = new int[mid + 1];
        dp[0] = 0;
        for (int i = 0; i < nums.length; i ++) {
            // 状态压缩，就必须要先物品，在背包容量，同时背包容量需要倒叙，从后往前。注意 j >= nums[i]
            for (int j = mid; j >= nums[i]; j --) {
                dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
            }
        }
        return dp[mid] == mid ? true : false;
    }
}

// https://leetcode-cn.com/problems/last-stone-weight-ii/
// 基本和上题相同，分差不多的两堆
class Solution {
    public int lastStoneWeightII(int[] stones) {
        int sum = 0;
        for (int stone : stones) {
            sum += stone;
        }
        int target = sum / 2;
        int[] dp = new int[target + 1];
        dp[0] = 0;
        for (int i = 0; i < stones.length; i ++) {
            for (int j = target; j >= stones[i]; j --) {
                dp[j] = Math.max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - dp[target] - dp[target];
    }
}

// https://leetcode-cn.com/problems/target-sum/
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum < target) return 0;
        if ((sum - target) % 2 != 0) return 0;
        int mid = (sum - target) / 2;
        int[] dp = new int[mid + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i ++) {
            for (int j = mid; j >= nums[i]; j --) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[mid];
    }
}

// 代码对比
// 0-1 背包
for (int i = 0; i < weight.length; i ++) {
    // 0-1 背包，从后往前，确保每个物品只添加一次
    for (int j = bagWeight; j >= weight[i]; j --) { 
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}
// 完全背包
for (int i = 0; i < weight.length; i ++) {
    // 完全背包，从前往后，确保每个物品可以添加多次
    for (int j = weight[i]; j <= bagWeight; j ++) {
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

// 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
// 如果求排列数就是外层for遍历背包，内层for循环遍历物品

// https://leetcode-cn.com/problems/coin-change-2/
// 只需要求组合数，所以先物品，再背包
class Solution {
    public int change(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int i = 0; i < coins.length; i ++) {
            for (int j = coins[i]; j <= amount; j ++) {
                dp[j] += dp[j - coins[i]]; 
            }
        }
        return dp[amount];
    }
}

// https://leetcode-cn.com/problems/combination-sum-iv/
// 需要求排序，先背包，后物品
class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        // 先背包，所以 j 从 1 开始，这时需在后面判断 j 是否大于等于 nums[i]
        for (int j = 1; j <= target; j ++) {
            for (int i = 0; i < nums.length; i ++) {
                // 这里加上判断，只有 j 大于等于 nums[i] 才可以更新dp
                if (j >= nums[i]) {
                    dp[j] += dp[j - nums[i]];   
                }
            }
        }
        return dp[target];
    }
}

// https://leetcode-cn.com/problems/climbing-stairs/
// 本题需要求排序，所以先背包，后物品
class Solution {
    public int climbStairs(int n) {
        if (n == 1) return 1;
        int[] steps = new int[] {1, 2};
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int j = 3; j <= n; j ++) {
            for (int i = 0; i < steps.length; i ++) {
                if (j >= steps[i]) {
                    dp[j] += dp[j - steps[i]];
                }
            }
        }
        return dp[n];
    }
}

// https://leetcode-cn.com/problems/coin-change/
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount + 1];
        // 初始化 dp
        for (int i = 0; i < amount + 1; i ++) {
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = 0;
        for (int i = 0; i < coins.length; i ++) {
            for (int j = coins[i]; j <= amount; j ++) {
                // 判断 dp[j - coins[i]] 有没有值，即 dp[j - coins[i]] 能否被数组组合成
                if (dp[j - coins[i]] != Integer.MAX_VALUE) {
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

// https://leetcode-cn.com/problems/perfect-squares/
// 跟上题差不多，注意 for 循环里面的条件
class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        for (int i = 0; i <= n; i ++) {
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = 0;
        for (int i = 1; i * i <= n; i ++) {
            for (int j = i * i; j <= n; j ++) {
                dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        }
        return dp[n];
    }
}

// https://leetcode-cn.com/problems/word-break/
// dp[i] 代表字符串 s 的 i 位置之前都可以凑成
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // 用 HashSet 保证 wordDict 里面值唯一
        Set<String> wordDictSet = new HashSet<>(wordDict);
        int len = s.length();
        boolean[] dp = new boolean[len + 1];
        dp[0] = true;
        for (int j = 1; j <= len; j ++) {
            for (int i = 0; i < j; i ++) {
                // 判断 wordDictSet 字符串 s 有没有 i 以后的字符
                if (dp[i] && wordDictSet.contains(s.substring(i, j))) {
                    dp[j] = true;
                    // 当可以组成就 break 跳出
                    break;
                }
            }
        }
        return dp[len];
    }
}

// https://leetcode-cn.com/problems/house-robber/
class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if (len == 0) return 0;
        if (len == 1) return nums[0];
        int[] dp = new int[len + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= len; i ++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
        }
        return dp[len];
    }
}

// https://leetcode-cn.com/problems/house-robber-ii/
// 本题相较上题，多了一个条件，那就是首尾两个值不能同时得到，所以可以将 nums 分为分别包括首和尾的两个部分
class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if (len == 0) return 0;
        if (len == 1) return nums[0];
        int[] dp1 = new int[len];
        int[] dp2 = new int[len];
        // 初始化 dp1 
        dp1[0] = 0;
        dp1[1] = nums[0];
        for (int i = 2; i < len; i ++) {
            dp1[i] = Math.max(dp1[i - 1], dp1[i - 2] + nums[i - 1]);
        }
        // 初始化 dp2
        dp2[0] = 0;
        dp2[1] = nums[1];
        for (int i = 2; i < len; i ++) {
            dp2[i] = Math.max(dp2[i - 1], dp2[i - 2] + nums[i]);
        }
        // 最后取两种条件下的最大值
        return Math.max(dp1[len - 1], dp2[len - 1]);
    }
}

// https://leetcode-cn.com/problems/house-robber-iii/
// 树形 DP 的入门题，用一个长度为 2 的 int 数组维护抢或不抢两种状态下的该节点的最大值
class Solution {
    public int rob(TreeNode root) {
        int[] res = robTree(root);
        return Math.max(res[0], res[1]);
    }
    int[] robTree(TreeNode root) {
        if (root == null) return new int[] {0, 0};
        int[] left = robTree(root.left);
        int[] right = robTree(root.right);
        int res1 = root.val + left[0] + right[0];
        int res2 = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[] {res2, res1};
    }
}

// 暴力解法 每个节点会被访问两次，会超时
class Solution {
	public int rob(TreeNode* root) {
        if (root == NULL) return 0;
        if (root->left == NULL && root->right == NULL) return root->val;
        // 偷父节点
        int val1 = root->val;
        if (root->left) val1 += rob(root->left->left) + rob(root->left->right); // 跳过root->left，相当于不考虑左孩子了
        if (root->right) val1 += rob(root->right->left) + rob(root->right->right); // 跳过root->right，相当于不考虑右孩子了
        // 不偷父节点
        int val2 = rob(root->left) + rob(root->right); // 考虑root的左右孩子
        return max(val1, val2);
        }
    }

// 带记忆版 每个节点只会访问一次
class Solution {
    Map<TreeNode, Integer> map = new HashMap<>();

    public int rob(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) return root.val;
        if (map.containsKey(root)) return map.get(root);
        // 偷父节点
        int res1 = root.val;
        if (root.left != null) 
            res1 += rob(root.left.left) + rob(root.left.right);
        if (root.right != null)
            res1 += rob(root.right.left) + rob(root.right.right);
        // 不偷父节点
        int res2 = rob(root.left) + rob(root.right);
        // 记录
        int res = Math.max(res1, res2);
        map.put(root, res);
        return res;
    }
}

// https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
// 记录状态，只有持有股票和不持有股票两种状态
class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][2];
        // [0]-[1] 表示 持有股票、不持有股票
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < prices.length; i ++) {
            dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[prices.length - 1][1];
    }
}

class Solution {
    public int maxProfit(int[] prices) {
        int min = prices[0];
        int[] dp = new int[prices.length];
        dp[0] = 0;
        for (int i = 1; i < prices.length; i ++) {
            dp[i] = Math.max(dp[i - 1], prices[i] - min);
            if (prices[i] < min)
                min = prices[i];
        }
        return dp[prices.length - 1];
    }
}

// 由于整个循环只用到两个值可以简化，后续类似，不过用 dp 数组简单好理解
class Solution {
    public int maxProfit(int[] prices) {
        int min = prices[0];
        int res = 0;
        int prev = 0;
        for (int i = 1; i < prices.length; i ++) {
            res = Math.max(prev, prices[i] - min);
            if (prices[i] < min)
                min = prices[i];
            prev = res;
        }
        return res;
    }
}

// https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
// 记录状态，只有持有股票和不持有股票两种状态
class Solution {
    public int maxProfit(int[] prices) {
        int[][] dp = new int[prices.length][2];
        // [0]-[1] 表示 持有股票、不持有股票
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < prices.length; i ++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
        }
        return dp[prices.length - 1][1];
    }
}

// 与上题不同的是本题可以多次买卖，所以需要累加
class Solution {
    public int maxProfit(int[] prices) {
        int[] dp = new int[prices.length];
        dp[0] = 0;
        int tmp = prices[0];
        for (int i = 1; i < prices.length; i ++) {
            if (prices[i] > tmp) {
                dp[i] = dp[i - 1] + prices[i] - tmp;
            } else {
                dp[i] = dp[i - 1];
            }
            tmp = prices[i];
        }
        return dp[prices.length - 1];
    }
}

// https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
// 比之前的难，每个点一共有 5 种状态，判断到达这几种状态时最大的收入
class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length == 0) return 0;
        int[][] dp = new int[prices.length][5];
        // 0-4 表示 无操作、第一次买入、第一次卖出、第二次买入、第二次卖出
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;
        dp[0][3] = -prices[0];
        dp[0][4] = 0;
        for (int i = 1; i < prices.length; i ++) {
            dp[i][0] = dp[i - 1][0];
            dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
            dp[i][2] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][2]);
            dp[i][3] = Math.max(dp[i - 1][2] - prices[i], dp[i - 1][3]);
            dp[i][4] = Math.max(dp[i - 1][3] + prices[i], dp[i - 1][4]);
        }
        return dp[prices.length - 1][4];
    }
}

// https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/
// 本题算是上题的普适版本，也是把所有状态列出，只不过用 for 循环处理
class Solution {
    public int maxProfit(int k, int[] prices) {
        if (prices.length == 0) return 0;
        int[][] dp = new int[prices.length][2 * k + 1];
        for (int j = 1; j < 2 * k + 1; j += 2)   
            dp[0][j] = -prices[0];
        for (int i = 1; i < prices.length; i ++) {
            dp[i][0] = dp[i - 1][0];
            for (int j = 1; j < 2 * k + 1; j += 2)   
                dp[i][j] = Math.max(dp[i - 1][j - 1] - prices[i], dp[i - 1][j]);
            for (int j = 2; j < 2 * k + 1; j += 2)
                dp[i][j] = Math.max(dp[i - 1][j - 1] + prices[i], dp[i - 1][j]);
        }
        return dp[prices.length - 1][2 * k];
    }
}

// https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
// 本题也需要分状态，每一天对应四种状态，要分开讨论
class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int[][] dp = new int[len][4];
        // 0-3 表示 无操作（不是冷却期）、无操作（冷却期）、买入、卖出
        dp[0][0] = 0;
        dp[0][1] = 0;
        dp[0][2] = -prices[0];
        dp[0][3] = 0;
        for (int i = 1; i < len; i ++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
            dp[i][1] = dp[i - 1][3];
            // 买入状态可以保持
            dp[i][2] = Math.max(dp[i - 1][2], Math.max(dp[i - 1][0], dp[i - 1][1]) - prices[i]);
            // 卖出状态不可用保持，卖出后就进入冷却期状态
            dp[i][3] = dp[i - 1][2] + prices[i];
        }
        return Math.max(dp[len - 1][0], Math.max(dp[len - 1][1], dp[len - 1][3]));
    }
}

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        int[][] dp = new int[len][3];
        // 0-3 表示 无操作、买入、卖出
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        dp[0][2] = 0;
        for (int i = 1; i < len; i ++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][2]);
            dp[i][1] = Math.max(dp[i - 1][1], Math.max(dp[i - 1][0], dp[i - 1][2]) - prices[i]);
            dp[i][2] = dp[i - 1][1] + prices[i];
        }
        return Math.max(dp[len - 1][0], dp[len - 1][2]);
    }
}

// https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int[][] dp = new int[prices.length][2];
        // 两种状态，持有股票、不持有股票
        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        for (int i = 1; i < prices.length; i ++) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
        }
        return dp[prices.length - 1][1];
    }
}

// https://leetcode-cn.com/problems/longest-increasing-subsequence/
class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums.length <= 1) return nums.length;
        int[] dp = new int[nums.length];
        for (int i = 0; i < nums.length; i ++) 
            dp[i] = 1;
        int res = 0;
        for (int i = 1; i < nums.length; i ++) {
            for (int j = 0; j < i; j ++)
                if (nums[i] > nums[j])
                    dp[i] = Math.max(dp[i], dp[j] + 1);
            if (dp[i] > res)
                res = dp[i];
        }
        return res;
    }
}

// https://leetcode-cn.com/problems/longest-common-subsequence/
class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];
        // 初始化 dp[0][...] 和 dp[...][0] 为 0
        for (int i = 1; i <= text1.length(); i ++) {
            char char1 = text1.charAt(i - 1);
            for (int j = 1; j <= text2.length(); j ++) {
                char char2 = text2.charAt(j - 1);
                if (char1 == char2) {
                    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[text1.length()][text2.length()];
    }
}

// https://leetcode-cn.com/problems/uncrossed-lines/
// 跟上题，最长公共子序列一模一样
class Solution {
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        for (int i = 1; i <= nums1.length; i ++) {
            int tmp1 = nums1[i - 1];
            for (int j = 1; j <= nums2.length; j ++) {
                int tmp2 = nums2[j - 1];
                if (tmp1 == tmp2) {
                    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[nums1.length][nums2.length];
    }
}

// https://leetcode-cn.com/problems/longest-continuous-increasing-subsequence/
// 本题与 最长递增子序列 区别在于，本题只需要比较连续的两个值是否递增，不递增就归 1；而最长递增子序列需要比较前面的每一个数，所有需要 for 循环
class Solution {
    public int findLengthOfLCIS(int[] nums) {
        if (nums.length == 0) return 0;
        int res = 1;
        int[] dp = new int[nums.length];
        for (int i = 0; i < nums.length; i ++) {
            dp[i] = 1;
        }
        for (int i = 1; i < nums.length; i ++) {
            if (nums[i] > nums[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            }
            if (dp[i] > res) res = dp[i];
        }
        return res;
    }
}

// https://www.nowcoder.com/questionTerminal/b65b8b1376d94d4b8d4718ba2f4c0022?toCommentId=9612441
// 本题需要自己去映射一个新的数组
import java.util.*;
public class Main {
    /*
    更改题目   a=[D,B,C,A]; b=[A,B,C,D]
    对 b 做映射  A->0; B->1; C->2; D->3
    那么对应的 a 可根据映射规则更改为 a'=[3,1,2,0]
    之后对 a' 做最长连续上升子数组即可
    */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; i ++) a[i] = sc.nextInt();
        for (int i = 0; i < n; i ++) b[i] = sc.nextInt();
        // 对 A 里面的数进行重新映射
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i ++) map.put(b[i], i);
        // 利用映射规则对 B 进行更新映射
        for (int i = 0; i < n; i ++) a[i] = map.get(a[i]);
        // 对更改之后的 b 做最长连续上升子序列
        int res = 0;
        int cur = 1;
        for (int i = 1; i < n; i ++) {
            if (a[i]>a[i-1]) {
                cur += 1;
                res = Math.max(res, cur);
            } else cur = 1;
        }
        System.out.println(n - res);
    }
}

// https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/
// 本题与 最长公共子序列 的区别在于，当加入的两个值不相同，最长公共子序列 会选 dp[i - 1][j] 和 dp[i][j - 1] 的最大值；而本题是令其为 0
class Solution {
    public int findLength(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        int res = 0;
        for (int i = 1; i <= nums1.length; i ++) {
            int tmp1 = nums1[i - 1];
            for (int j = 1; j <= nums2.length; j ++) {
                int tmp2 = nums2[j - 1];
                if (tmp1 == tmp2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    if (dp[i][j] > res)
                        res = dp[i][j];
                }
            }
        }
        return res;
    }
}

// https://leetcode-cn.com/problems/maximum-subarray/
// 本题 dp 的更新条件是选取（该点值，该点值+之前值之和）的最大值
class Solution {
    public int maxSubArray(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.length; i ++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            if (dp[i] > res) 
                res = dp[i];
        }
        return res;
    }
}

// https://leetcode-cn.com/problems/is-subsequence/
class Solution {
    public boolean isSubsequence(String s, String t) {
        // dp[i][j] 表示 s 中 i 位置前的与 t 中 j 位置前的字符相同的个数是多少
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        for (int i = 1; i <= s.length(); i ++) {
            for (int j = 1; j <= t.length(); j ++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    // 新加入的字符不同时的递推公式
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
        if (dp[s.length()][t.length()] == s.length()) return true;
        return false;
    }
}

// https://leetcode-cn.com/problems/distinct-subsequences/
// 当把问题抽象成距离问题，这题就比较模板化了，跟上题差不多，区别是新加入的两个字符相同时的更新规则；以及初始化规则
class Solution {
    public int numDistinct(String s, String t) {
        if (s.length() < t.length()) return 0;
        int[][] dp = new int[s.length() + 1][t.length() + 1];
        // 当 t 为空，怎么都有 1 种解法
        for (int i = 0; i <= s.length(); i ++) 
            dp[i][0] = 1;
        for (int i = 1; i <= s.length(); i ++) {
            for (int j = 1; j <= t.length(); j ++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    // 新加入的两个字符相同时，更新时需要加上的是 dp[i -1][j]，区别上题的 1.
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[s.length()][t.length()];
    }
}

// https://leetcode-cn.com/problems/delete-operation-for-two-strings/
// 一步到位，dp 代表相同需要删除多少步
class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        // 初始化 dp
        for (int i = 1; i <= word1.length(); i ++) 
            dp[i][0] = i;
        for (int j = 1; j <= word1.length(); j ++) 
            dp[0][j] = j;
        for (int i = 1; i <= word1.length(); i ++) {
            char tmp1 = word1.charAt(i - 1);
            for (int j = 1; j <= word2.length(); j ++) {
                char tmp2 = word2.charAt(j - 1);
                if (tmp1 == tmp2) 
                    dp[i][j] = dp[i - 1][j - 1];
                else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]) + 1, dp[i - 1][j - 1] + 2);
                }
            }
        }
        return dp[word1.length()][word2.length()];
    }   
}

// 先求最长公共子序列，然后再求删除多少步
class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 1; i <= word1.length(); i ++) {
            char tmp1 = word1.charAt(i - 1);
            for (int j = 1; j <= word2.length(); j ++) {
                char tmp2 = word2.charAt(j - 1);
                if (tmp1 == tmp2) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return word1.length() + word2.length() - 2 * dp[word1.length()][word2.length()];
    }
}

// https://leetcode-cn.com/problems/edit-distance/
// 最难的编辑问题，可以增删改，定义 dp 为达到相同所需的操作。递推公式中，当新加入的两个字符一样，则 dp[i][j] = dp[i-1][j-1]；如果新加入的两个字符不一样，那么可分为增删改三种情况，当中，对一个增相当于对另一个删，所以这两种可以归为一种情况，那么可归纳为 1.对 word1 增；2.对 word2 增；3.同时增，取这三种情况的最小值 + 1.
class Solution {
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        // 初始化
        for (int i = 1; i <= word1.length(); i ++) 
            dp[i][0] = i;
        for (int j = 1; j <= word2.length(); j ++) 
            dp[0][j] = j;
        for (int i = 1; i <= word1.length(); i ++) {
            char tmp1 = word1.charAt(i - 1);
            for (int j = 1; j <= word2.length(); j ++) {
                char tmp2 = word2.charAt(j - 1);
                if (tmp1 == tmp2) {
                    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[word1.length()][word2.length()];
    }
}

// 定义 dp 为是否为回文子串
class Solution {
    public int countSubstrings(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        int res = 0;
        for (int j = 1; j < s.length(); j ++) {
            char tmp = s.charAt(j);
            for (int i = 0; i < j; i ++) {
                if (s.charAt(i) == tmp && (j - i <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    res ++;
                }
            }
        }
        return res;
    }
}
// 另外一种处理方式
// 回文子串的处理，首先注意 i 的起始位置，i 表示左边边界，所以从尾巴开始倒着循环
class Solution {
    public int countSubstrings(String s) {
        boolean[][] dp = new boolean[s.length()][s.length()];
        // 初始化，由于要统计 true 的个数，所以不初始化
        int res = 0;
        for (int i = s.length() - 1; i >= 0; i --) {
            for (int j = i; j < s.length(); j ++) {
                if (s.charAt(i) == s.charAt(j) && (j - i <= 1 || dp[i + 1][j - 1])) {
                        dp[i][j] = true;
                        res += 1;
                    }
                }
            }
        }
        return res;
    }
}

// https://leetcode-cn.com/problems/longest-palindromic-subsequence/
class Solution {
    public int longestPalindromeSubseq(String s) {
        int[][] dp = new int[s.length()][s.length()];
        // 初始化
        for (int i = 0; i < s.length(); i ++) 
            dp[i][i] = 1;
        for (int i = s.length() - 1; i >= 0; i --) {
            // 右边界不跟左边界重合       
            for (int j = i + 1; j < s.length(); j ++) {
                if (s.charAt(i) == s.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][s.length() - 1];
    }
}

class Solution {
    public String longestPalindrome(String s) {
        int left = 0, right = 0, maxLen = 1;
        boolean[][] dp = new boolean[s.length()][s.length()];
        for (int j = 1; j < s.length(); j ++) {
            int tmp = s.charAt(j);
            for (int i = 0; i < j; i ++) {
                if (s.charAt(i) == tmp && (j - i <= 2 || dp[i + 1][j - 1])) {
                    dp[i][j] = true;
                    if (j - i + 1 > maxLen) {
                        left = i;
                        right = j;
                        maxLen = j - i + 1;
                    }
                }
            }
        }
        return s.substring(left, right + 1);
    }
}