> 技术文档 > 动态规划 力扣hot100热门面试算法题 面试基础 核心思路 背题

动态规划 力扣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; }}