【LeetCode Hot100】动态规划篇
前言
本文用于整理LeetCode Hot100中题目解答，因题目比较简单且更多是为了面试快速写出正确思路，只做简单题意解读和一句话题解方便记忆。但代码会全部给出，方便大家整理代码思路。
70. 爬楼梯
一句话题意
每次爬1or2，问爬到n的路径方法数。
一句话题解
滚动数组。
class Solution {public int climbStairs(int n) {int[] dp=new int[2];dp[0]=1; //1dp[1]=2; //2for(int i=3;i<=n;i++){dp[(i+1)%2]=dp[0]+dp[1];}return dp[(n+1)%2];}
}118. 杨辉三角
一句话题意
杨辉三角。
一句话题解
杨辉三角每个位置的值等于上面两个的和。
class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> ans = new ArrayList<>();for(int i=0;i<numRows;i++){ans.add(new ArrayList<>());ans.get(i).add(1);for(int j=1;j<i+1;j++){if(j==i)ans.get(i).add(1);else ans.get(i).add(ans.get(i-1).get(j-1)+ans.get(i-1).get(j));}}return ans;}
}198. 打家劫舍
一句话题意
在不能连续取数组中两个数字的情况下，能取得最大值是多少。
一句话题解
当前位置的值只能由前一个位置或者前前个位置加当前位置的值。
class Solution {public int rob(int[] nums) {int n=nums.length;if(n==1)return nums[0];int[] dp = new int[n];dp[0]=nums[0];dp[1]=Math.max(nums[1],nums[0]);int ans=Math.max(dp[0],dp[1]);for(int i=2;i<n;i++){dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);}return dp[n-1];}
}279. 完全平方数
一句话题意
给定一个整数n，问该数最少可以用几个完全平方数组成。
一句话题解
类似于完全背包问题，我们每次从小问题往大问题归即可。
class Solution {public int numSquares(int n) {int[] dp =new int[n+1];for(int i=1;i<=n;i++){dp[i]=Integer.MAX_VALUE;for(int j=1;j*j<=i;j++){dp[i]=Math.min(dp[i],dp[i-j*j]+1);}}return dp[n];}
}322. 零钱兑换
一句话题意
给定一个整数数组代表硬币，每个硬币有无限个，然后给定个目标值，问最少要用多少个硬币凑出目标值。
一句话题解
完全背包。
class Solution {public int coinChange(int[] coins, int amount) {int n = coins.length;int[] dp=new int[amount+1];Arrays.fill(dp,amount+1);dp[0]=0;for(int i=0;i<n;i++){for(int j=coins[i];j<=amount;j++){dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);}}if(dp[amount]>amount)return -1;return dp[amount];}
}139. 单词拆分
一句话题意
给定一个字符串和一个字符串序列，问字符串是否能被字符串序列中的字符串组合出来。
一句话题解
枚举断点，看当前断点是否能被序列中的字符串组成。
class Solution {public boolean wordBreak(String s, List<String> wordDict) {Set<String> u = new HashSet<>();for(String ss:wordDict)u.add(ss);boolean[] dp=new boolean[s.length()+1];dp[0]=true;for(int i=1;i<=s.length();i++){for(int j=0;j<i;j++){if(dp[j]&&u.contains(s.substring(j,i))){dp[i]=true;break;}}}return dp[s.length()];}
}300. 最长递增子序列
一句话题意
给定一个序列，求LIS。
一句话题解
low数组优化，设定一个递减序列，每次用二分查找当前值在序列中的位置，能替换替换，如果比整个low数组都大就扔进low数组最后。
class Solution {public int lengthOfLIS(int[] nums) {int n=nums.length;List<Integer> low = new ArrayList<>();for(int i=0;i<n;i++){int l=0;int r=low.size();while(l<r){int mid=l+(r-l>>1);int x=low.get(mid);if(x<nums[i]){l=mid+1;}else{r=mid;}}if(l==low.size())low.add(nums[i]);else low.set(l,nums[i]);}return low.size();}
}152. 乘积最大子数组
一句话题意
求给定一个数组，求数组中乘积最大的子数组（子数组是连续的）。
一句话题解
从前往后算一次，从后往前算一次，肯定能取到最大成绩，注意取到0的时候归回1。
class Solution {public int maxProduct(int[] nums) {int ans=nums[0];int a=1;for(int i=0;i<nums.length;i++){a*=nums[i];ans=Math.max(a,ans);if(nums[i]==0)a=1;}a=1;for(int i=nums.length-1;i>=0;i--){a*=nums[i];ans=Math.max(a,ans);if(nums[i]==0)a=1;}return ans;}
}416. 分割等和子集
一句话题意
给定一个数组，问数组是否能被分为两个sum相等的子集。
一句话题解
我们可以先计算出整个的和，如果为偶数则可以初步证明是可分的，且能求出来目标值。然后转化成0-1背包来考虑即可。
class Solution {public boolean canPartition(int[] nums) {int n=nums.length;int sum=0;for(int i=0;i<n;i++)sum+=nums[i];if(sum%2!=0)return false;sum/=2;boolean[] dp=new boolean[sum+1];dp[0]=true;for(int i=0;i<n;i++){for(int j=sum;j>=nums[i];j--){dp[j]|=dp[j-nums[i]];}}return dp[sum];}
}32. 最长有效括号
一句话题意
给定一个括号序列，求最长的有效括号序列。
一句话题解
栈，对于遇到的'('直接扔进去，如果是')'则能弹出弹出，然后计算，不能弹出的话就直接扔进去做隔断。
class Solution {public int longestValidParentheses(String s) {int ans=0;Deque<Integer> u=new LinkedList<Integer>();u.push(-1);for(int i=0;i<s.length();i++){if(s.charAt(i)=='('){u.push(i);}else {u.pop();if(u.size()==0){u.push(i);}else{ans=Math.max(ans,i-u.peek());}}}return ans;}
}