编辑距离
解法一
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; } }