class Solution {
    public int minDistance(String word1, String word2) {
        int n1 = word1.length();
        int n2 = word2.length();
        int[][] dp = new int[n1 + 1][n2 + 1];
        // 第一行
        for (int j = 1; j <= n2; j++) dp[0][j] = dp[0][j - 1] + 1;
        // 第一列
        for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + 1;
        for (int i = 1; i <= n1; i++) {
            for (int j = 1; j <= n2; 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 - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
            }
        }
        return dp[n1][n2];  
    }
}

class Solution {
    public boolean canPartition(int[] nums) {
        int len = nums.length;
        if (len < 2) return false;
        int sum = 0;
        int max = 0;
        for(int i : nums){
            max = Math.max(max,i);
            sum+=i;
        }
        if(sum %2 != 0) return false;
        int target = sum/2;
        if(max > target) return false;
        if(max == target) return true;
        //dp[i][j]  数组表示的是在0-i中，背包容量为j的最大价值
        int dp[][] = new int[len+1][target+1];
        for(int i = 1;i <= len;i++){        
            for(int j = 1;j <= target;j++){
                if(j >= nums[i-1]){
                    dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-nums[i-1]]+nums[i-1]);
                }else{
                    dp[i][j] = dp[i-1][j];
                }
            }
        }
        if(dp[len][target] == target) return true;
        return false;
    }
}

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int dp[] = new int[s.length()+1];
        dp[0] = 1;
        for(int i = 1;i <= s.length();i++){
            for(int j = 0;j < i;j++){
                if(dp[j] == 1 && wordDict.contains(s.substring(j,i))){
                    dp[i] = 1;
                    break;
                }
            }
        }
        return dp[s.length()] == 1;
    }
}