LeetCode Hot100(动态规划）

70. 爬楼梯

题目：

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

题解：

不难发现，每一次都是从i-1或者i-2爬上来的，我们加起来求和即可

 class Solution {public int climbStairs(int n) {int []arr=new int[n+2];arr[1]=1;arr[2]=2;for(int i=3;i<=n;i++){arr[i]=arr[i-1]+arr[i-2];}return arr[n];}
}

118. 杨辉三角

题目：

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。

题解：

根据题意模拟即可

 class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>>arr=new ArrayList<>();for(int i=0;i<numRows;i++){List<Integer>list=new ArrayList<>();for(int j=0;j<=i;j++){if(j==0||j==i){list.add(1);}else{list.add(arr.get(i-1).get(j-1)+arr.get(i-1).get(j));}}arr.add(list);}return arr;}
}

198. 打家劫舍

题目：

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

题解

由于相连房屋不可以进行相连盗窃，就会出现两种情况1001或者101，那么我们设dpi1为盗窃当前房屋的最大值，该值需要加上前面i-1的没有盗窃的最大值，同理dpi2为没有盗窃的，需要加上前面1，2取一个最大值即可

class Solution {public int rob(int[] nums) {int ans=0;int [][]dp= new int[nums.length+2][2];dp[0][0]=0;dp[0][1]=nums[0];for(int i=1;i<nums.length;i++){dp[i][0]=Math.max(dp[i-1][1],dp[i-1][0]);dp[i][1]=Math.max(nums[i]+dp[i-1][0],dp[i-1][1]);}return Math.max(dp[nums.length-1][0],dp[nums.length-1][1]);}
}

279. 完全平方数

题目

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

题解

我们发现最大值只有1e4，所以我们的最大平方数就是100了，然后我们就认为每一个数都由1-100之中的某几个组成，也就是一个完全背包问题了，枚举即可

class Solution {public int numSquares(int n) {int []brr=new int[200];for(int i=1;i<=100;i++){brr[i]=i*i;}int []dp=new int[n+2];for(int i=1;i<=n;i++){dp[i]=10000;}for(int i=1;i<=100;i++){for(int j=1;j<=n;j++){if(j>=brr[i]){dp[j]=Math.min(dp[j],dp[j-brr[i]]+1);}}}return dp[n];}
}

322. 零钱兑换

题意

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。你可以认为每种硬币的数量是无限的。

题解

跟上一题一样，跑完全背包即可，不过不需要记录次数了

class Solution {public int coinChange(int[] coins, int amount) {int []dp=new int[amount+10];for(int i=1;i<=amount;i++){dp[i]=amount+1;}for(int i=0;i<coins.length;i++){for(int j=0;j<=amount;j++){if(j>=coins[i]){dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);}}}if(dp[amount]==amount+1){return -1;}return dp[amount];}
}

139. 单词拆分

题意

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

题解

我们直接可以手动模拟，设置dpi是当前位置是否能够被拼接成功，那么我们每一次枚举到一个位置，就去枚举所有的字串，如果当前的字串能够完全的匹配i和i-length+1的字串，就去看看i-length是否可以，如果可以当前位置也就可以了

import java.util.*;import static java.util.Collections.reverse;class Solution {public static void main(String[] args) {List<String> list =new ArrayList<>();list.add("aaaaaa");list.add("aa");String s="aaaaaaa";wordBreak(s,list);}public static boolean wordBreak(String s, List<String> wordDict) {int []dp=new int[s.length()];char []arr=s.toCharArray();char [][]brr=new char[wordDict.size()][];for(int i=0;i<brr.length;i++){brr[i]=wordDict.get(i).toCharArray();}for(int i=0;i<arr.length;i++){//5 -5 4 3 2for(int j=0;j<brr.length;j++){int l=i-brr[j].length+1;if(l<0){continue;}int l2=0;int mark=1;while(l2<brr[j].length&&l<=i){if(brr[j][l2]!=arr[l]){mark=0;break;}l2++;l++;}if(mark==0){continue;}l=i-brr[j].length;if(l==-1||dp[l]==1){dp[i]=1;}}}if(dp[s.length()-1]==1){return true;}return false;}}

300. 最长递增子序列

题意

求一个序列的最长上升子序列

题解

模板题，可以直接背诵，有兴趣的同学可以在网上搜索证明

import java.util.*;import static java.util.Collections.reverse;class Solution {public static void main(String[] args) {}public int lengthOfLIS(int[] nums) {int []ans=new int[nums.length+3];if(nums.length==0){return 0;}int len=1;ans[1]=nums[0];for(int i=1;i<nums.length;i++){if(nums[i]>ans[len]){ans[++len]=nums[i];}else{ans[findx(ans,len,nums[i])]=nums[i];}}return len;}public static int findx(int []nums,int len,int x){int l=1;int r=len;while(l<=r){int mid=(l+r)>>1;if(nums[mid]>=x){r=mid-1;}else{l=mid+1;}}return l;}}

152. 乘积最大子数组

题意

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续 子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。测试用例的答案是一个 32-位 整数。

题解

我们发现存在负数，因为一个负数会让当前的值取反，那么我们维护一下到达当前位置的max和min即可

class Solution {public int maxProduct(int[] nums) {int[] dpMax = new int[nums.length];int[] dpMin = new int[nums.length];dpMax[0] = nums[0];dpMin[0] = nums[0];int maxProduct = nums[0];  for (int i = 1; i < nums.length; i++) {int candidate1 = dpMax[i-1] * nums[i]; int candidate2 = dpMin[i-1] * nums[i]; int currentNum = nums[i];            dpMax[i] = Math.max(currentNum, Math.max(candidate1, candidate2));dpMin[i] = Math.min(currentNum, Math.min(candidate1, candidate2));maxProduct = Math.max(maxProduct, dpMax[i]);}return maxProduct;}
}

416. 分割等和子集

题意

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

题解

我们由于只能分成两个集合，那么两个集合的和明显是总的和/2 ，记录总和为sum，每个数组的和也就是sum/2，又发现，每个元素只能拿一个，那我们如果能够抽起来sum/2就可以了，去跑一便01背包

import java.util.Arrays;public class Solution {public static void main(String[] args) {}public boolean canPartition(int[] nums) {int sum = Arrays.stream(nums).sum();if(sum%2==1){return false;}int n=sum/2;int []dp=new int[n+2];dp[0]=1;for(int i=0;i<nums.length;i++){for(int j=n;j>=0;j--){if(nums[i]>j){break;}dp[j]=dp[j-nums[i]]|dp[j];}}return dp[n]==1?true:false;
//        return false;}public static int findx(int []nums,int len,int x){int l=1;int r=len;while(l<=r){int mid=(l+r)>>1;if(nums[mid]>=x){r=mid-1;}else{l=mid+1;}}return l;}}

32. 最长有效括号

题意

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度

题解

感觉没有什么太好的做法，我直接用栈进行模拟的，看看当前位置是否是合理的，记录一下，最后求一个最长的子序列即可

import java.util.Arrays;
import java.util.Stack;public class Solution {public static void main(String[] args) {String s="(()";longestValidParentheses(s);}public static int longestValidParentheses(String s) {char []arr=s.toCharArray();Stack<node>brr=new Stack<>();int []dp=new int[arr.length+1];for(int i=0;i<arr.length;i++){node now=new node();now.id=i;now.f=arr[i];if(brr.isEmpty()){brr.push(now);}else if(now.f=='('){brr.push(now);}else {if(brr.peek().f=='('){dp[brr.peek().id]=1;dp[i]=1;brr.pop();}else{brr.push(now);}}}System.out.println(Arrays.toString(dp));int maxx=0;for(int i=0;i<arr.length;i++){if(i==0||dp[i]==0){continue;}else{dp[i]=dp[i]+(dp[i-1]==0?0:dp[i-1]);maxx=Math.max(dp[i],maxx);}}return maxx;}public static class node{int id;char f;}}