动态规划 对于动态规划问题,拆解为如下五步曲
确定dp数组(dp table)以及下标的含义
确定递推公式
dp数组如何初始化
确定遍历顺序
举例推导dp数组
01背包问题 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i],得到的价值是value[i] 。每件物品只能用一次 ,求解将哪些物品装入背包里物品价值总和最大。
二维01背包解法 还是用动态规划五部曲:
1.确定dp dp[i] [j]表示任意选取前i个物品放进容量为j的背包的最大价值 2.确定递推公式 dp[i][j] = Math.max(dp[i - 1] [j], dp[i-1] [j - weight[i]] + value[i]) 3.dp数组如何初始化 第一列为0 dp[i][0] = 0; 第一行容量大于weight[0]的话,dp[0] [j] = value[0] 4.确定遍历顺序 先遍历物品 在遍历背包,这样好理解 其实反过来也可以 5.举例推导dp数组
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 import java.util.*;public class Main { public static void main (String[] args) { Scanner in = new Scanner(System.in); int m = in.nextInt(); int n = in.nextInt(); int [] weight = new int [m]; int [] value = new int [m]; for (int i = 0 ; i < m; i++) { weight[i] = in.nextInt(); } for (int i = 0 ; i < m; i++) { value[i] = in.nextInt(); } int [][] dp = new int [m][n + 1 ]; for (int j = weight[0 ]; j <= n; j++) { dp[0 ][j] = value[0 ]; } for (int i = 1 ; i < m; i++) { for (int j = 0 ; j <= n; j++) { if (j < weight[i]) dp[i][j] = dp[i - 1 ][j]; else dp[i][j] = Math.max(dp[i - 1 ][j], dp[i - 1 ][j - weight[i]] + value[i]); } } System.out.println(dp[m - 1 ][n]); } }
一维01背包解法 1.确定dp dp[j]表示容量为j的背包的最大价值 2.确定递推公式 dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]) 3.dp数组如何初始化 dp[0] = 0 4.确定遍历顺序 一维dp遍历的时候,背包是从大到小。倒序遍历是为了保证物品i只被放入一次 ,如果一旦正序遍历了,那么物品0就会被重复加入多次!如果遍历背包容量放在上一层,那么每个dp[j]就只会放入一个物品,即:背包里只放入了一个物品。 5.举例推导dp数组
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 import java.util.*;public class Main { public static void main (String[] args) { Scanner sc = new Scanner(System.in); int M = sc.nextInt(); int N = sc.nextInt(); int []weights = new int [M]; int []values = new int [M]; for (int i = 0 ; i < M; i++){ weights[i] = sc.nextInt(); } for (int i = 0 ; i < M; i++){ values[i] = sc.nextInt(); } int [] dp = new int [N + 1 ]; for (int i = 0 ; i < M; i++) { for (int j = N; j >= weights[i]; j--) { dp[j] = Math.max(dp[j], values[i] + dp[j - weights[i]]); } } System.out.println(dp[N]); sc.close(); } }
完全背包问题 完全背包和01背包问题唯一不同的地方就是,每种物品有无限件 。01背包和完全背包唯一不同就是体现在遍历顺序上,01背包内嵌的循环是从大到小遍历,为了保证每个物品仅被添加一次。
而完全背包的物品是可以添加多次的,所以要从小到大去遍历。
如果求组合数就是外层for循环遍历物品,内层for遍历背包 。
如果求排列数就是外层for遍历背包,内层for循环遍历物品 。
1 2 3 4 5 6 for (int i = 0 ; i < weight.size(); i++) { for (int j = weight[i]; j <= bagWeight ; j++) { dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } }
在完全背包中,对于一维dp数组来说,其实两个for循环嵌套顺序是无所谓的 ,因为dp[j] 是根据 下标j之前所对应的dp[j]计算出来的。 只要保证下标j之前的dp[j]都是经过计算的就可以了。
1 2 3 4 5 6 for (int j = 0 ; j <= bagWeight; j++) { for (int i = 0 ; i < weight.size(); i++) { if (j - weight[i] >= 0 ) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); } }
322. 零钱兑换 322. 零钱兑换
给你一个整数数组 coins
,表示不同面额的硬币;以及一个整数 amount
,表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -1
。
你可以认为每种硬币的数量是无限的
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public int coinChange (int [] coins, int amount) { int n = coins.length; int max = Integer.MAX_VALUE; int [] dp = new int [amount + 1 ]; for (int i = 0 ; i <= amount; i++) { dp[i] = max; } dp[0 ] = 0 ; for (int i = 0 ; i < n; i++) { for (int j = coins[i]; j <= amount; j++) { if (dp[j - coins[i]] != max) dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1 ); } } return dp[amount] == max ? -1 : dp[amount]; } }
279. 完全平方数 279. 完全平方数
给你一个整数 n
,返回 和为 n
的完全平方数的最少数量 。
完全平方数 是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1
、4
、9
和 16
都是完全平方数,而 3
和 11
不是。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public int numSquares (int n) { int [] dp = new int [n + 1 ]; for (int i = 0 ; i <= n; i++) { dp[i] = 10001 ; } dp[0 ] = 0 ; for (int i = 0 ; i < Math.sqrt(n) + 1 ; i++) { for (int j = i * i; j <= n; j++) { dp[j] = Math.min(dp[j], dp[j - i * i] + 1 ); } } return dp[n]; } }
139. 单词拆分 139. 单词拆分
给你一个字符串 s
和一个字符串列表 wordDict
作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s
则返回 true
。
注意: 不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
解法:背包五部曲
另外这里的遍历顺序要注意:
“apple”, “pen” 是物品,那么我们要求 物品的组合一定是 “apple” + “pen” + “apple” 才能组成 “applepenapple”。
“apple” + “apple” + “pen” 或者 “pen” + “apple” + “apple” 是不可以的,那么我们就是强调物品之间顺序。
所以说,本题一定是 先遍历 背包,再遍历物品。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 class Solution { public boolean wordBreak (String s, List<String> wordDict) { boolean [] dp = new boolean [s.length() + 1 ]; dp[0 ] = true ; for (int i = 1 ; i <= s.length(); i++) { for (String word : wordDict) { int len = word.length(); if (i >= len && dp[i - len] && word.equals(s.substring(i - len, i))) { dp[i] = true ; break ; } } } return dp[s.length()]; } }
1143. 最长公共子序列 1143. 最长公共子序列
给定两个字符串 text1
和 text2
,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0
。
一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。
例如,"ace"
是 "abcde"
的子序列,但 "aec"
不是 "abcde"
的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
解法:
s1[i] == s2[j] : f[i][j]=f[i−1] [j−1]+1。代表必然使用 s1[i] 与 s2[j] 时 LCS 的长度。 s1[i] != s2[j] : f[i][j]=max(f[i−1] [j],f[i][j−1])。代表必然不使用 s1[i](但可能使用s2[j])时 和 必然不使用 s2[j](但可能使用s1[i])时 LCS 的长度。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution { public int longestCommonSubsequence (String text1, String text2) { int m = text1.length(), n = text2.length(); int [][] dp = new int [m + 1 ][n + 1 ]; for (int i = 1 ; i <= m; i++) { for (int j = 1 ; j <= n; j++) { if (text1.charAt(i - 1 ) == text2.charAt(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 ]); } } return dp[m][n]; } }
152. 乘积最大子数组 152. 乘积最大子数组
给你一个整数数组 nums
,请你找出数组中乘积最大的非空连续子数组(该子数组中至少包含一个数字),并返回该子数组所对应的乘积。测试用例的答案是一个 32-位 整数。
解法:
假设nums[i]是正数:如果 dp[i - 1] 是负数,那最大值就是nums[i]; dp[i - 1] 是正数,最大值就是nums[i - 1] *dp[i - 1]。
假设nums[i]是负数:dp[i - 1] 是正数的时候,越乘越小,最大值是nums[i];dp[i - 1] 是负数的时候,越乘越大,最大值是nums[i] * dp[i-1],但是dp[i-1]可能会被大的正值替换掉,所以需要保存最小的值;于是我们可能就需要记录一下负数的那个最小数。例如 -2 ,3,-2.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 class Solution { public int maxProduct (int [] nums) { int n = nums.length; int [][] dp = new int [n][2 ]; dp[0 ][0 ] = nums[0 ]; dp[0 ][1 ] = nums[0 ]; for (int i = 1 ; i < n; i++) { if (nums[i] >= 0 ) { dp[i][1 ] = Math.max(nums[i], dp[i - 1 ][1 ] * nums[i]); dp[i][0 ] = Math.min(nums[i], dp[i - 1 ][0 ] * nums[i]); } else { dp[i][1 ] = Math.max(nums[i], dp[i - 1 ][0 ] * nums[i]); dp[i][0 ] = Math.min(nums[i], dp[i - 1 ][1 ] * nums[i]); } } int ans = dp[0 ][1 ]; for (int i = 1 ; i < n; i++) { ans = Math.max(ans, dp[i][1 ]); } return ans; } }
72. 编辑距离 72. 编辑距离
给你两个单词 word1
和 word2
, 请返回将 word1
转换成 word2
所使用的最少操作数 。
你可以对一个单词进行如下三种操作:
解法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public int minDistance (String word1, String word2) { int m = word1.length(), n = word2.length(); int [][] dp = new int [m + 1 ][n + 1 ]; for (int i = 1 ; i <= m; i++) { dp[i][0 ] = i; } for (int j = 1 ; j <= n; j++) { dp[0 ][j] = j; } for (int i = 1 ; i <= m; i++) { for (int j = 1 ; j <= n; j++) { if (word1.charAt(i - 1 ) == word2.charAt(j - 1 )) { dp[i][j] = dp[i - 1 ][j - 1 ]; } else { dp[i][j] = Math.min(Math.min(dp[i - 1 ][j], dp[i][j - 1 ]), dp[i - 1 ][j - 1 ]) + 1 ; } } } return dp[m][n]; } }
32. 最长有效括号 32. 最长有效括号
给你一个只包含 '('
和 ')'
的字符串,找出最长有效(格式正确且连续)括号子串的长度。
解法一:动态规划
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public int longestValidParentheses (String s) { int n = s.length(); int ans = 0 ; int [] dp = new int [n]; for (int i = 1 ; i < n; i++) { if (s.charAt(i) == ')' ) { if (s.charAt(i - 1 ) == '(' ) { dp[i] = (i >= 2 ? 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 ; } ans = Math.max(ans, dp[i]); } } return ans; } }
解法二:栈
对于遇到的每个 ‘(’ ,我们将它的下标放入栈中 对于遇到的每个 ‘)’ ,我们先弹出栈顶元素表示匹配了当前右括号: 如果栈为空,说明当前的右括号为没有被匹配的右括号,我们将其下标放入栈中来更新我们之前提到的最后一个没有 被匹配的右括号的下标 如果栈不为空,当前右括号的下标减去栈顶元素即为以该右括号为结尾的最长有效括号的长度
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public int longestValidParentheses (String s) { int ans = 0 ; Deque<Integer> stack = new ArrayDeque<Integer>(); stack.push(-1 ); for (int i = 0 ; i < s.length(); i++) { if (s.charAt(i) == '(' ) { stack.push(i); } else { stack.pop(); if (stack.isEmpty()) { stack.push(i); } else { ans = Math.max(ans, i - stack.peek()); } } } return ans; } }