509、斐波那契数
class Solution {
public int fib(int n) {
// 方法一：递归
// if(n==0){
// return 0;
// }else if(n==1){
// return 1;
// }else{
// return fib(n-1)+fib(n-2);
// }
// 方法二：动态规划
if(n<=1) return n;
int[] dp = new int[2];
dp[0] = 0;
dp[1] = 1;
int sum = 0;;
for(int i = 2; i <= n; i++){
sum = dp[0] + dp[1];
dp[0] = dp[1];
dp[1] = sum;
}
return dp[1];
}
}
70、爬楼梯
class Solution {
public int climbStairs(int n) {
if(n==1) return n;
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for(int i = 3; i <= n; i++){
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
}
746、使用最小花费爬楼梯
class Solution {
public int minCostClimbingStairs(int[] cost) {
int[] dp = new int[cost.length + 1];
dp[0] = 0;
dp[1] = 0;
for(int i = 2; i <= cost.length; i++){
dp[i] = Math.min(dp[i - 1] + cost[i - 1],dp[i - 2] + cost[i - 2]);
}
return dp[cost.length];
}
}
62、 不同路径
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
dp[0][0] = 1;
for(int i = 1; i < m; i++){
dp[i][0] = 1;
}
for(int j = 1; 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];
}
}
63、不同路径 II
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
if(obstacleGrid[0][0] == 1){
return 0;
}else{
dp[0][0] = 1;
}
for(int i = 1; i < m; i++){
if(obstacleGrid[i][0] == 1){
break;
}else{
dp[i][0] = 1;
}
}
for(int j = 1; j < n; j++){
if(obstacleGrid[0][j] == 1){
break;
}else{
dp[0][j] = 1;
}
}
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
if(obstacleGrid[i][j] == 1){
continue;
}else{
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}
}
343、整数拆分
class Solution {
public int integerBreak(int n) {
// 方法一：贪心
// if(n == 2){
// return 1;
// }else if(n == 3){
// return 2;
// }
// int result = 1;
// while(n > 0){
// if(n > 4){
// result *= 3;
// n = n - 3;
// }else if(n == 4){
// result *= 4;
// break;
// }else if(n == 3 || n == 2){
// result *= n;
// break;
// }
// }
// return result;
// 方法二：动态规划
int[] dp = new int[n + 1];
dp[2] = 1;
for(int i = 3; i <= n; i++){
for(int j = 1; j <= i - j; j++){
dp[i] = Math.max(dp[i],Math.max(j*(i - j),j*dp[i - j]));
}
}
return dp[n];
}
}
96、不同的二叉搜索树
class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; i++){
for(int j = 1; j <= i; j++){
dp[i] += dp[j - 1] * dp[i - j];
}
}
return dp[n];
}
}
416、分割等和子集
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for(int i = 0; i < nums.length; i++){
sum += nums[i];
}
if(sum%2==1){
return false;
}else{
sum = sum/2;
}
Arrays.sort(nums);
int[][] dp = new int[nums.length][sum + 1];
for(int i = nums[0]; i <= sum; i++){
dp[0][i] = nums[0];
}
for(int i = 1; i < nums.length; i++){
for(int j = 1; j <= sum; j++){
if(nums[i] > j){
dp[i][j] = dp[i - 1][j];
}else{
dp[i][j] = Math.max(dp[i - 1][j], nums[i] + dp[i - 1][j - nums[i]]);
}
}
}
return dp[nums.length - 1][sum] == sum;
}
}
1049、最后一块石头的重量 II
class Solution {
public int lastStoneWeightII(int[] stones) {
int target = 0;
for(int i : stones){
target += i;
}
int sum = target/2;
int[][] dp = new int[stones.length][sum + 1];
for(int i = stones[0]; i <= sum; i++){
dp[0][i] = stones[0];
}
for(int i = 1; i < stones.length; i++){
for(int j = 1; j <= sum; j++){
if(j < stones[i]){
dp[i][j] = dp[i - 1][j];
}else{
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - stones[i]] + stones[i]);
}
}
}
return target - 2 * dp[stones.length - 1][sum];
}
}
494、目标和
class Solution {
public int findTargetSumWays(int[] nums, int target) {
int sum = 0;
for(int i:nums){
sum += i;
}
if(Math.abs(target) > sum) return 0;
if((sum + target) % 2 == 1) return 0;
int bageSize = (sum + target) / 2;
int[] dp = new int[bageSize + 1];
dp[0] = 1;
for(int i = 0; i < nums.length; i++){
for(int j = bageSize; j >= nums[i]; j--){
dp[j] += dp[j - nums[i]];
}
}
return dp[bageSize];
}
}
474、一和零
class Solution {
public int findMaxForm(String[] strs, int m, int n) {
int[][] dp = new int[m + 1][n + 1];
for(String str : strs){
int zeroNum = 0;
int oneNum = 0;
for(char c: str.toCharArray()){
if(c == '0'){
zeroNum++;
}else{
oneNum++;
}
}
for(int i = m; i >= zeroNum; i--){
for(int j = n; j >= oneNum; j--){
dp[i][j] = Math.max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
}
}
}
return dp[m][n];
}
}
518、 零钱兑换 II
class Solution {
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for(int i = 0; i < coins.length; i++){
for(int j = coins[i]; j <= amount; j++){
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
}
377、组合总和 Ⅳ
class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp = new int[target + 1];
dp[0] = 1;
for(int i = 1; i <= target; i++){
for(int j = 0; j < nums.length; j++){
if(i >= nums[j]){
dp[i] += dp[i - nums[j]];
}
}
}
return dp[target];
}
}
322、零钱兑换
class Solution {
public int coinChange(int[] coins, int amount) {
int max = Integer.MAX_VALUE;
int[] dp = new int[amount + 1];
for(int i = 0; i < dp.length; i++){
dp[i] = max;
}
dp[0] = 0;
for(int i = 0; i <= amount; i++){
for(int j = 0; j < coins.length; j++){
if(i >= coins[j] && dp[i - coins[j]] != max){
dp[i] = Math.min(dp[i - coins[j]] + 1, dp[i]);
}
}
}
return dp[amount]==max?-1:dp[amount];
}
}
279、完全平方数
class Solution {
public int numSquares(int n) {
// 创建物品
int length = (int)Math.floor(Math.sqrt(n));
int[] nums = new int[length];
for(int i = 0; i < length; i++){
nums[i] = (i + 1) * (i + 1);
}
int[] dp = new int[n + 1];
int max = Integer.MAX_VALUE;
for(int j = 0; j < dp.length; j++){
dp[j] = max;
}
dp[0] = 0;
for(int i = 0; i < nums.length; i++){
for(int j = nums[i]; j <= n; j++){
dp[j] = Math.min(dp[j], dp[j - nums[i]] + 1);
}
}
return dp[n];
}
}
139、单词拆分
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
HashSet<String> set = new HashSet<>(wordDict);
boolean[] valid = new boolean[s.length() + 1];
valid[0] = true;
for(int i = 1; i <= s.length(); i++){
for(int j = 0; j < i && !valid[i]; j++){
if(set.contains(s.substring(j, i)) && valid[j]){
valid[i] = true;
}
}
}
return valid[s.length()];
}
}
198、打家劫舍
class Solution {
public int rob(int[] nums) {
if(nums.length == 1) return nums[0];
int[] dp = new int[nums.length];
dp[0] = nums[0];
dp[1] = Math.max(dp[0], nums[1]);
for(int i = 2; i < nums.length; i++){
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[nums.length - 1];
}
}
213、打家劫舍 II
class Solution {
public int rob(int[] nums) {
if(nums.length == 1) return nums[0];
return Math.max(robAction(nums, 0, nums.length - 2), robAction(nums, 1, nums.length - 1));
}
public int robAction(int[] nums, int start, int end){
if(start == end) return nums[start];
int[] dp = new int[nums.length];
dp[start] = nums[start];
dp[start + 1] = Math.max(dp[start], nums[start + 1]);
for(int i = start + 2; i <= end; i++){
dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[end];
}
}
337、打家劫舍 III
class Solution {
public int rob(TreeNode root) {
// 后序遍历
int[] res = robAction(root);
return Math.max(res[0], res[1]);
}
public int[] robAction(TreeNode root){
int[] res = new int[2];
if(root == null) return res;
int[] left = robAction(root.left);
int[] right = robAction(root.right);
res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
res[1] = root.val + left[0] + right[0];
return res;
}
}
121、买卖股票的最佳时机
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
if(len == 1) return 0;
int[][] dp = new int[len][2];
dp[0][0] = -prices[0];
dp[0][1] = 0;
for(int i = 1; i < len; i++){
dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
}
return dp[len - 1][1];
}
}
122、买卖股票的最佳时机 II
class Solution {
public int maxProfit(int[] prices) {
// 贪心
// int max = 0;
// for(int i = 1; i < prices.length; i++){
// if(prices[i] > prices[i - 1]){
// max += prices[i] - prices[i - 1];
// }
// }
// return max;
// 动态规划
int len = prices.length;
if(len == 1) return 0;
int[][] dp = new int[len][2];
dp[0][0] = -prices[0];
dp[0][1] = 0;
for(int i = 1; i < len; i++){
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] -prices[i]);
dp[i][1] = Math.max(dp[i - 1][0] + prices[i], dp[i - 1][1]);
}
return dp[len - 1][1];
}
}
123、买卖股票的最佳时机 III
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
int[][] dp = new int[len][5];
dp[0][1] = -prices[0];
dp[0][3] = -prices[0];
for(int i = 1; i < len; i++){
dp[i][1] = Math.max(-prices[i], dp[i - 1][1]);
dp[i][2] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][2]);
dp[i][3] = Math.max(dp[i - 1][2] - prices[i], dp[i - 1][3]);
dp[i][4] = Math.max(dp[i - 1][3] + prices[i], dp[i - 1][4]);
}
return dp[len - 1][4];
}
}
188、买卖股票的最佳时机 IV
class Solution {
public int maxProfit(int k, int[] prices) {
int len = prices.length;
int[][] dp = new int[len][1 + 2 * k];
for(int i = 1; i < 1 + 2 * k; i = i + 2){
dp[0][i] = -prices[0];
}
for(int i = 1; i < len; i++){
for(int j = 1; j < 1 + 2 * k; j++){
if(j == 1){
dp[i][j] = Math.max(-prices[i], dp[i - 1][1]);
}else if(j%2==0){
dp[i][j] = Math.max(dp[i - 1][j - 1] + prices[i], dp[i - 1][j]);
}else{
dp[i][j] = Math.max(dp[i - 1][j - 1] - prices[i], dp[i - 1][j]);
}
}
}
return dp[len - 1][2 * k];
}
}
309、最佳买卖股票时机含冷冻期
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
if(len == 1) return 0;
int[][] dp = new int[len][4];
dp[0][0] = -prices[0];
for(int i = 1; i < len; i++){
dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][1], dp[i - 1][3]) - prices[i]);
dp[i][1] = Math.max(dp[i - 1][3], dp[i - 1][1]);
dp[i][2] = dp[i - 1][0] + prices[i];
dp[i][3] = dp[i - 1][2];
}
return Math.max(dp[len - 1][1], Math.max(dp[len - 1][2], dp[len - 1][3]));
}
}
714、买卖股票的最佳时机含手续费
class Solution {
public int maxProfit(int[] prices, int fee) {
// 贪心
// if(prices.length==1){
// return 0;
// }
// int index = prices[0]+fee;
// int sum=0;
// for(int i = 1; i < prices.length; i++){
// if(prices[i]>index){
// sum+=prices[i]-index;
// index=prices[i];
// }else if(prices[i]+fee<index){
// index=prices[i]+fee;
// }
// }
// return sum;
// 动态规划
int len = prices.length;
if(len == 1) return 0;
int[][] dp = new int[len][2];
dp[0][0] = -prices[0];
dp[0][1] = 0;
for(int i = 1; i < len; i++){
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] -prices[i]);
dp[i][1] = Math.max(dp[i - 1][0] + prices[i] - fee, dp[i - 1][1]);
}
return Math.max(dp[len - 1][1],dp[len - 1][0]);
}
}
300、最长递增子序列
class Solution {
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp,1);
int result = 1;
for(int i = 1; i < nums.length; i++){
for(int j = 0; j < i; j++){
if(nums[i] > nums[j]) dp[i] = Math.max(dp[i], dp[j] + 1);
}
if(dp[i] > result) result = dp[i];
}
return result;
}
}
674、最长连续递增序列
class Solution {
public int findLengthOfLCIS(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp,1);
int result = 1;
int index = 0;
for(int i = 1; i < nums.length; i++){
index = nums[i];
for(int j = i - 1; j >= 0; j--){
if(index <= nums[j]){
break;
}else{
dp[i] = dp[i] + 1;
index = nums[j];
}
}
if(dp[i] > result) result = dp[i];
}
return result;
}
}
718、最长重复子数组
class Solution {
public int findLength(int[] nums1, int[] nums2) {
int[][] dp = new int[nums1.length + 1][nums2.length + 1];
int result = 0;
for(int i = 1; i <= nums1.length; i++){
for(int j = 1; j <= nums2.length; j++){
if(nums1[i - 1] == nums2[j - 1]){
dp[i][j] = dp[i - 1][j - 1] + 1;
}
if(dp[i][j] > result) result = dp[i][j];
}
}
return result;
}
}
1143、最长公共子序列
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
char[] nums1 = text1.toCharArray();
char[] nums2 = text2.toCharArray();
int[][] dp = new int[nums1.length + 1][nums2.length + 1];
int result = 0;
for(int i = 1; i <= nums1.length; i++){
for(int j = 1; j <= nums2.length; j++){
if(nums1[i - 1] == nums2[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]);
}
if(dp[i][j] > result) result = dp[i][j];
}
}
return result;
}
}
1035、不相交的线
class Solution {
public int maxUncrossedLines(int[] nums1, int[] nums2) {
int[][] dp = new int[nums1.length + 1][nums2.length + 1];
int result = 0;
for(int i = 1; i <= nums1.length; i++){
for(int j = 1; j <= nums2.length; j++){
if(nums1[i - 1] == nums2[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]);
}
if(dp[i][j] > result) result = dp[i][j];
}
}
return result;
}
}
53、最大子数组和
class Solution {
public int maxSubArray(int[] nums) {
// 贪心
// if(nums.length == 1){
// return nums[0];
// }
// int count = 0;
// int sum = Integer.MIN_VALUE;
// for(int i = 0; i < nums.length; i++){
// count += nums[i];
// sum = Math.max(sum, count);
// if(count <= 0){
// count = 0;
// }
// }
// return sum;
// 动态规划
int[] dp = new int[nums.length];
dp[0] = nums[0];
int result = nums[0];
for(int i = 1; i < nums.length; i++){
dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
result = dp[i] > result ? dp[i] : result;
}
return result;
}
}
392、 判断子序列
class Solution {
public boolean isSubsequence(String s, String t) {
char[] nums1 = s.toCharArray();
char[] nums2 = t.toCharArray();
int[][] dp = new int[nums1.length + 1][nums2.length + 1];
int result = 0;
for(int i = 1; i <= nums1.length; i++){
for(int j = 1; j <= nums2.length; j++){
if(nums1[i - 1] == nums2[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]);
}
if(dp[i][j] > result) result = dp[i][j];
}
}
return result == s.length();
}
}
115、不同的子序列
class Solution {
public int numDistinct(String s, String t) {
char[] nums1 = s.toCharArray();
char[] nums2 = t.toCharArray();
int[][] dp = new int[nums1.length + 1][nums2.length + 1];
for(int i = 0; i < nums1.length; i++){
dp[i][0] = 1;
}
for(int i = 1; i <= nums1.length; i++){
for(int j = 1; j <= nums2.length; j++){
if(nums1[i - 1] == nums2[j - 1]){
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
}else{
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[nums1.length][nums2.length];
}
}
583、两个字符串的删除操作
class Solution {
public int minDistance(String word1, String word2) {
char[] nums1 = word1.toCharArray();
char[] nums2 = word2.toCharArray();
int[][] dp = new int[nums1.length + 1][nums2.length + 1];
int result = 0;
for(int i = 1; i <= nums1.length; i++){
for(int j = 1; j <= nums2.length; j++){
if(nums1[i - 1] == nums2[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]);
}
if(dp[i][j] > result) result = dp[i][j];
}
}
return word1.length() + word2.length() - 2 * result;
}
}
72、编辑距离
class Solution {
public int minDistance(String word1, String word2) {
char[] nums1 = word1.toCharArray();
char[] nums2 = word2.toCharArray();
int[][] dp = new int[nums1.length + 1][nums2.length + 1];
int result = 0;
for(int i = 0; i <= nums1.length; i++){
dp[i][0] = i;
}
for(int i = 0; i <= nums2.length; i++){
dp[0][i] = i;
}
for(int i = 1; i <= nums1.length; i++){
for(int j = 1; j <= nums2.length; j++){
if(nums1[i - 1] == nums2[j - 1]){
dp[i][j] = dp[i - 1][j - 1];
}else{
dp[i][j] = Math.min(dp[i - 1][j], Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;;
}
}
}
return dp[nums1.length][nums2.length];
}
}
647、回文子串
class Solution {
public int countSubstrings(String s) {
boolean[][] dp = new boolean[s.length()][s.length()];
for(int i = s.length() - 1; i >= 0; i--){
for(int j = i; j < s.length(); j++){
if(s.charAt(i) == s.charAt(j)){
if(j - i < 3){
dp[i][j] = true;
}else{
dp[i][j] = dp[i + 1][j - 1];
}
}else{
dp[i][j] = false;
}
}
}
int count = 0;
for (int i = 0; i < s.length(); i++) {
for (int j = 0; j < s.length(); j++) {
if (dp[i][j]) count++;
}
}
return count;
}
}
516、最长回文子序列
class Solution {
public int longestPalindromeSubseq(String s) {
int[][] dp = new int[s.length() + 1][s.length() + 1];
int result = 1;
for(int i = s.length() - 1; i >= 0; i--){
dp[i][i] = 1;
for(int j = i + 1; j < s.length(); j++){
if(s.charAt(i) == s.charAt(j)){
dp[i][j] = dp[i + 1][j - 1] + 2;
}else{
dp[i][j] = Math.max(dp[i][j], Math.max(dp[i + 1][j], dp[i][j - 1]));
}
result = result > dp[i][j] ? result : dp[i][j];
}
}
return result;
}
}
739、每日温度
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int lens = temperatures.length;
int[] res = new int[lens];
Stack<Integer> stack = new Stack<>();
stack.push(0);
for(int i = 1; i < lens; i++){
if(temperatures[i] <= temperatures[stack.peek()]){
stack.push(i);
}else{
while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){
int temp = stack.pop();
res[temp] = i - temp;
}
stack.push(i);
}
}
return res;
}
}
496、下一个更大元素 I
class Solution {
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
int lens = nums1.length;
int[] res = new int[lens];
Arrays.fill(res,-1);
Stack<Integer> stack = new Stack<>();
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int i = 0 ; i< nums1.length ; i++){
hashMap.put(nums1[i],i);
}
stack.push(0);
for(int i = 1; i < nums2.length; i++){
if(nums2[i] <= nums2[stack.peek()]){
stack.push(i);
}else{
while(!stack.isEmpty() && nums2[i] > nums2[stack.peek()]){
if (hashMap.containsKey(nums2[stack.peek()])){
Integer index = hashMap.get(nums2[stack.peek()]);
res[index] = nums2[i];
}
stack.pop();
}
stack.push(i);
}
}
return res;
}
}
503、下一个更大元素 II
class Solution {
public int[] nextGreaterElements(int[] nums) {
int lens = nums.length;
int[] res = new int[lens];
Arrays.fill(res,-1);
Stack<Integer> stack = new Stack<>();
stack.push(0);
for(int i = 1; i < 2*lens; i++){
if(nums[i%lens] <= nums[stack.peek()]){
stack.push(i%lens);
}else{
while(!stack.isEmpty() && nums[i%lens] > nums[stack.peek()]){
int temp = stack.pop();
res[temp] = nums[i%lens];
}
stack.push(i%lens);
}
}
return res;
}
}
[42]
[84]