菜鸡的原地踏步史03(◐‿◑)

每日一念
改掉自己想到哪写哪的坏习惯

一维动态规划
爬楼梯

class Solution {/**dp[i] 爬到第i个台阶有dp[i]种爬法dp[i] - dp[i - 1] + 1 & dp[i - 2] + 2*/public int climbStairs(int n) {int[] dp = new int[n + 1];dp[0] = 1;dp[1] = 1;for(int i = 2; i <= n; i++) {dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
}

杨辉三角

class Solution {/**res.get(i)表示第i层的数组首尾设置为1res.get(i).get(j) = res.get(i - 1).get(j - 1) + res.get(i - 1).get(j)*/public List<List<Integer>> generate(int numRows) {List<List<Integer>> res = new ArrayList();List<Integer> path = new ArrayList();for(int i = 0; i < numRows; i++) {for(int j = 0; j <= i; j++) {if(j == 0 || j == i) {path.add(1);}else {path.add(0);}}res.add(path);path = new ArrayList();}for(int i = 2; i < res.size(); i++) {for(int j = 1; j < res.get(i).size() - 1; j++) {int val = res.get(i - 1).get(j - 1) + res.get(i - 1).get(j);res.get(i).set(j, val);// System.out.println(res.get(i).get(j));}}return res;}
}

打家劫舍

class Solution {/**dp[i]表示第i家能偷到的最高金额dp[i] -- dp[i - 1], dp[i - 2] + nums[i - 1]*/// dp[nums.length]public int rob(int[] nums) {if(nums.length == 0) {return 0;}if(nums.length == 1) {return nums[0];}int[] dp = new int[nums.length];dp[0] = 0;dp[1] = nums[0];for(int i = 2; i < dp.length; i++) {dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);}return Math.max(dp[nums.length - 1], dp[nums.length - 2] + nums[nums.length - 1]);}// dp[nums.length + 1]public int rob(int[] nums) {if(nums.length == 0) {return 0;}if(nums.length == 1) {return nums[0];}int[] dp = new int[nums.length];dp[0] = 0;dp[1] = nums[0];for(int i = 2; i < dp.length; i++) {dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);}return Math.max(dp[nums.length - 1], dp[nums.length - 2] + nums[nums.length - 1]);}
}

完全平方数

class Solution {/**dp[i] 组成和为i的完全平方数最少数量 -- dp[i - j *j]从 < i 的第一个完全平方数开始找dp数组需要的最长长度为n + 13 = 1 + 1 + 1 全1组成*/public int numSquares(int n) {int[] dp = new int[n + 1];Arrays.fill(dp, n);dp[0] = 0;for(int i = 0; i <= n; i++){for(int j = 0; j * j <= i; j++) {dp[i] = Math.min(dp[i], dp[i - j *j] + 1);}}return dp[n];}
}

零钱兑换

class Solution {/**dp[i] 面值为i的零钱最少可以兑换的硬币数不可达值设置成amount + 1*/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 < dp.length; i++) {for(int coin: coins) {if(i >= coin) {dp[i] = Math.min(dp[i], dp[i - coin] + 1);}else {continue;}}}return dp[amount] == amount + 1 ? -1 : dp[amount];}
}/**不可达值设置成-1*/public int coinChange(int[] coins, int amount) {int[] dp = new int[amount + 1];Arrays.fill(dp, -1); // 不可达值dp[0] = 0;for(int i = 0; i < dp.length; i++) {for(int coin: coins) {if(i == coin) {dp[i] = 1;}else if(i > coin) {if(dp[i - coin] == -1) {continue;}else {if(dp[i] == -1) {dp[i] = dp[i - coin] + 1;}else {dp[i] = Math.min(dp[i], dp[i - coin] + 1);}}}}}return dp[amount];}
}

单词拆分

class Solution {/**dp[i] 表示前i个字符的组合，可以被字典拼接成boolean类型的数组dp[s.len + 1]dp[j]  + substring(j, i) -- 在word里面*/public boolean wordBreak(String s, List<String> wordDict) {Set<String> map = new HashSet(wordDict);boolean[] dp = new boolean[s.length() + 1];dp[0] = true;for(int i = 1; i < dp.length; i++) {for(int j = 0; j < i; j++) {if(dp[j] && map.contains(s.substring(j, i))) {dp[i] = true;break;}}}return dp[s.length()];}
}

最长递增子序列

class Solution {/**dp[i] 表示元素i结束的最长子序列*/public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length];Arrays.fill(dp, 1);for(int i = 1; i < dp.length; i++) {for(int j = 0; j < i; j++) {if(nums[i] > nums[j]) {dp[i] = Math.max(dp[i], dp[j] + 1);}}}int maxlen = Integer.MIN_VALUE;for(int i = 0; i < dp.length; i++) {if(dp[i] > maxlen) {maxlen = dp[i];}}return maxlen;}
}

乘积最大子数组

分割等和子集

class Solution {/**boolean dp[i] 前i个数字是否存在子集和为i*/public boolean canPartition(int[] nums) {int sum = Arrays.stream(nums).sum();if(sum % 2 != 0) {return false;}int mid = sum/2;boolean[] dp = new boolean[mid + 1];dp[0] = true;for(int i = 1; i < nums.length; i++) {for(int j = dp.length - 1; j >= nums[i - 1]; j--) {if(dp[j - nums[i - 1]]) {dp[j] = true;}}}return dp[mid];}
}

二维动态规划
不同路径

class Solution {/**dp[i][j] 表示从start点走到(i, j)的位置，总共有多少条不同路径dp[i][j]  dp[i - 1][j] 向右  dp[i][j - 1] 向下*/public int uniquePaths(int m, int n) {int[][] dp = new int[m][n];for(int i = 0; i < m; i++) {dp[i][0] = 1;}for(int j = 0; j < n; j++) {dp[0][j] = 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 - 1][n - 1];}
}

最小路径和

class Solution {/**dp[i][j]表示从左上角到(i, j)位置的最小数字总和dp[i][j] 只能由d[i - 1][j]向右，        或者d[i][j - 1]向下dp[i - 1][j] + nums[i][j]     dp[i][j - 1] + nums[i][j]   */public int minPathSum(int[][] grid) {int m = grid.length;int n = grid[0].length;int[][] dp = new int[m][n];dp[0][0] = grid[0][0];for(int i = 1; i < m; i++) {dp[i][0] = dp[i - 1][0] + grid[i][0];}for(int j = 1; j < n; j++) {dp[0][j] = dp[0][j - 1] + grid[0][j];}for(int i = 1; i < m; i++) {for(int j = 1; j < n; j++) {dp[i][j] = Math.min(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j]);}}return dp[m - 1][n - 1];}
}

最长回文子串

class Solution {/**dp[i] 以字符串的第i个位置的字母结尾的最长回文子串不太理解双指针法能写判断是否回文子串 奇数 i 向两边扩散, 偶数i i+1 向两边扩散*/public String longestPalindrome(String s) {String res = "";for(int i = 0; i < s.length(); i++) {String res1 = isPalindrome(s, i, i);String res2 = isPalindrome(s, i, i + 1);res = (res1.length() > res.length()) ? res1 : res;res = (res2.length() > res.length()) ? res2 : res;}return res;}public String isPalindrome(String s, int l, int r) {while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)) {l--;r++;}return s.substring(l + 1, r);}
}

最长公共子序列

class Solution {/**0 a b c d e0  0 0 0 0 0 0a  0 1 0 0 0 0b  0 1 2 2 2 2c  0 1 2 3 3 3dp[i][j] text1以i结尾的字符串，和text2以j结尾的字符串，最长匹配到的公共子序列i 和 j结尾的字符能匹配上text1.charAt(i-1) == text2.charAt(j - 1) ? dp[i - 1][j - 1] + 1不能匹配上 dp[i - 1][j], dp[i][j - 1]往前比较，取最大值*/public int longestCommonSubsequence(String text1, String text2) {int[][] dp = new int[text1.length() + 1][text2.length() + 1];for(int i = 1; i <= text1.length(); i++) {for(int j = 1; j <= text2.length(); j++) {if(text1.charAt(i - 1) == 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[text1.length()][text2.length()];}
}

编辑距离

class Solution {/**dp[i][j] 表示word1以i结尾的子串转换成word2以j结尾的子串需要的最少操作数初始化 dp[0][j] = jdp[i][0] = i0 h o r s e0  0 1 2 3 4 5r  1 1 o  2s  3i和j处的字符不相等dp[i][j] -- dp[i - 1][j] + 1 改i ? 增 or 删 or 替换-- dp[i][j - 1] + 1 改j-- dp[i - 1][j - 1] + 1 替换(i, j)i和j处的字符不相等*/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++) {for(int j = 1; j <= word2.length(); 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[word1.length()][word2.length()];}
}