动态规划 力扣hot100热门面试算法题 面试基础 核心思路 背题
动态规划
打家劫舍
https://leetcode.cn/problems/house-robber/
核心思路
状态表示: f[i]表示偷取前i家的最高金额。
状态转移: f[i] = Math.max(f[i-1],f[i-2] + nums[i]);
示例代码
class Solution { public int rob(int[] nums) { int n = nums.length; if(n==0) return 0; if(n==1) return nums[0]; if(n == 2) return Math.max(nums[0],nums[1]); int[] f =new int[n]; f[0] = nums[0];f[1] = Math.max(nums[0],nums[1]); for(int i = 2;i<n;i++){ f[i] = Math.max(f[i-2] + nums[i],f[i-1]); } return f[n-1]; }}
完全平方数
https://leetcode.cn/problems/perfect-squares/
核心思路
状态表示:f[i]: 和为 n 的完全平方数的最少数量 。
状态转移:集合{1,4,…},a*a<=n, f[i] = min(f[i],f[i-a]+1);
示例代码
class Solution { public int numSquares(int n) { int[] f = new int[n + 1]; f[0] = 0; for (int j = 1; j <= n; j++) { int min = n+1; for (int t = 1; t * t <= j; t++) { int x = t * t; min = Math.min(min, f[j - x]); } f[j] = min +1; } return f[n]; }}
零钱兑换
https://leetcode.cn/problems/coin-change/
核心思路
完全背包
示例代码
class Solution { public int coinChange(int[] coins, int amount) { if (amount == 0) return 0; int[] f = new int[amount + 1]; Arrays.fill(f,amount + 1); f[0] = 0; for (int i = 0; i < coins.length; i++) { for (int j = coins[i]; j < amount + 1; j++) { f[j] = Math.min(f[j], f[j - coins[i]] + 1); } } int x = f[amount]; return x >= amount + 1 ? -1 : x; }}
单词拆分
https://leetcode.cn/problems/word-break/
核心思路
若string 为 true,即f[n+1] = true,则string一定存在 倒数 j 个字母组成的单词 在词典中,且f[i-j]为true;
//f[i]表示s的前i-1个字母 是true or false
示例代码
class Solution { public boolean wordBreak(String s, List<String> wordDict) { Set<String> set = new HashSet<>(); //找到最大最小,为了减少多余判断,降低时间 int minString = 99999999;int maxString = -1; for (String word : wordDict){ set.add(word); int len = word.length(); minString = Math.min(minString,len); maxString = Math.max(maxString,len); } int n = s.length(); //f[i]表示s的前i-1个字母 是true or false boolean[] f = new boolean[n + 10]; f[0] = true; for(int i = 0;i < n;i++){ if(i + 1 <minString) continue; for(int j = i+1 -minString;j >=i + 1 -maxString && j>=0;j--){ if(set.contains(s.substring(j,i+1)) && f[j]){ f[i+1] = true; break; } } } return f[n]; }}
最长递增子序列
https://leetcode.cn/problems/longest-increasing-subsequence/
核心思路
状态表示:f[i]表示所有以第i个数结尾的上升子序列的集合,值为最长递增子序列的长度;
状态转移:集合s 为 nums数组前i-1个数比nums[i]小的所有元素,元素记为a,
f[i] = Math.max(f[i],f[a]+1);
示例代码
class Solution { public int lengthOfLIS(int[] nums) { int n = nums.length; int[] f = new int[n]; //f[i]表示所有以第i个数结尾的上升子序列的集合,值为最长递增子序列的长度 for(int i = 0;i< n;i++){ f[i] = 1; //遍历nums[i]之前的数,if(nums[j]<nums[i]),将f[j]与nums[i]拼接在一起 for(int j = 0;j<i;j++){ if(nums[j]<nums[i]) f[i] = Math.max(f[i],f[j]+1); } } int res = 0; for(int i = 0;i< n;i++) if(f[i]>res) res = f[i]; return res; }}
乘积最大子数组
https://leetcode.cn/problems/maximum-product-subarray/
核心思路
因为nums中可能有负数,所以不仅要维护当前最大值,也要维护当前最小值,因为最小的负数*一个负数可能成最大值。
示例代码
class Solution { public int maxProduct(int[] nums) { int ans = Integer.MIN_VALUE; // 注意答案可能是负数 int fMax = 1; int fMin = 1; for (int x : nums) { int mx = fMax; fMax = Math.max(Math.max(fMax * x, fMin * x), x); fMin = Math.min(Math.min(mx * x, fMin * x), x); ans = Math.max(ans, fMax); } return ans; }}
分割等和子集
https://leetcode.cn/problems/partition-equal-subset-sum/
核心思路
01背包:
f[i]表示,nums中的某些元素能否和为i;
状态转移:若f[i-nums[i]] 为 true,则f[i]为true;
此题就是寻找f[sum/2]是否为true。
示例代码
class Solution { public boolean canPartition(int[] nums) { int sum = 0; for (int i : nums) sum += i; if (sum % 2 != 0) return false; int n = nums.length; int target=sum/2; boolean[] f = new boolean[target+1]; f[0] = true; for (int i = 0; i < n; i++) for (int j = target; j >= nums[i]; j--) if(f[j - nums[i]]) f[j] = true; return f[target]; }}
最长有效括号
https://leetcode.cn/problems/longest-valid-parentheses/
核心思路
状态表示:dp[i]表示以s.charAt(i)结尾的有效子串长度
状态转移:dp[i] 来源于 dp[i-1];
如果dp[i-1] == ’ ( ’ , 那就 dp[i] = (i-2 >= 0? dp[i-2]: 0) + 2;
如果dp[i-1] == ’ ) ’ ,那就看看这个右括号对应的位置是否是左括号,
是的话就dp[i] = dp[i-1]+ (i-dp[i-1] >= 2? dp[i-dp[i-1]-2]: 0) +2;
示例代码
class Solution { public int longestValidParentheses(String s) { int len = s.length(); if(len == 0){ return 0; } //以s.charAt(i)结尾的有效子串长度 int []dp = new int[len]; dp[0] = 0; int max = 0; // 如果字串结尾为)才会有有效子串,会有...()()和...((()))两种情况 for(int i = 1; i < len; i++){ char c = s.charAt(i); if(c == \')\'){ if(s.charAt(i-1) == \'(\'){ dp[i] = (i-2 >= 0? dp[i-2]: 0) + 2; } else if(i-dp[i-1] > 0 && s.charAt(i-dp[i-1]-1) == \'(\'){ dp[i] = dp[i-1]+ (i-dp[i-1] >= 2? dp[i-dp[i-1]-2]: 0) +2; } } max = Math.max(max, dp[i]); } return max; }}
爬楼梯
https://leetcode.cn/problems/climbing-stairs/
核心思路
状态表示:dp[i]
爬到i阶的方法数
状态转移 dp[n] = dp[n-1] + dp[n-2]
示例代码
class Solution { public int climbStairs(int n) { if(n == 1) return 1; if(n == 2) return 2; int[] f = new int[n+1]; f[1] = 1;f[2] =2; for(int i = 3 ;i<= n;i++){ f[i] = f[i-1] + f[i-2]; } return f[n]; }}
杨辉三角
class Solution { public List<List<Integer>> generate(int n) { List<List<Integer>> ans = new ArrayList<>(); ans.add(List.of(1)); for(int i =1;i<n;i++){ List<Integer> row = new ArrayList<>(i+1); row.add(1); for(int j = 1;j < i;j++){ row.add(ans.get(i - 1).get(j - 1) + ans.get(i - 1).get(j)); } row.add(1); ans.add(row); } return ans; }}