https://leetcode-cn.com/tag/dynamic-programming/
题目汇总
322. 零钱兑换中等[✔]
338. 比特位计数中等
343. 整数拆分中等
354. 俄罗斯套娃信封问题困难（不会做）
357. 计算各个位数不同的数字个数中等
363. 矩形区域不超过 K 的最大数值和困难（没做）
368. 最大整除子集中等（没做）
375. 猜数字大小 II中等（题解能看懂，自己写不明白）
322. 零钱兑换中等
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回
-1。
示例 1:
输入: coins =[1, 2, 5], amount =11
输出:3
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins =[2], amount =3
输出: -1
说明:
你可以认为每种硬币的数量是无限的。
思路一：动态规划
class Solution {
public int coinChange(int[] coins, int amount) {//执行用时 :14 ms, 在所有 Java 提交中击败了85.58%的用户
if (coins == null || amount < 0) {
return -1;
}
if (amount == 0){
return 0;
}
int[] dp = new int[amount+1];//dp[i]=j表示凑够i元最少需要j枚硬币。数组长度设为（amount++1）保证可以访问dp[amount]
dp[0] = 0;
for(int i=1;i<amount+1;i++){//问题规模从小到大，直到达到目标面值
dp[i] = Integer.MAX_VALUE/2;//因为出现了Math.min的操作，所以在初始化的时候很重要，初始化为一个很大的数就可以了，但是dp[i] =Integer.MAX_VALUE是不可以的，计算dp[i-coin]+1就会出现溢出问题
for(int coin:coins){//遍历所有面值的硬币
if(i-coin >= 0 ){
dp[i] = Math.min(dp[i],dp[i-coin]+1);
}
}
}
return dp[amount] == Integer.MAX_VALUE/2 ? -1 : dp[amount];
}
}
思路二：贪心+DFS
这是在题解https://leetcode-cn.com/problems/coin-change/solution/322-by-ikaruga/
中看到的思路，这种思路能提高效率，但是自己想不到，摘抄一下代码。
class Solution {//执行用时 :3 ms, 在所有 Java 提交中击败了97.04%的用户
int ans = Integer.MAX_VALUE;
public int coinChange(int[] coins, int amount) {
Arrays.sort(coins);
coinChange(coins.length-1, coins, 0, amount);
return ans == Integer.MAX_VALUE ? -1 : ans;
}
private void coinChange(int index, int[] coins, int count, int needAmount) {
if (needAmount == 0) {
ans = Math.min(count, ans);
return;
}
if (index < 0) {
return;
}
int i = needAmount / coins[index];
//count+k<ans关键步骤，一直没怎么理解清楚
for (int k=i; k>=0 && count+k<ans; k--) {
coinChange(index-1, coins, count+k, needAmount-k*coins[index]);
}
}
}
338. 比特位计数中等
给定一个非负整数 num。对于 **0 ≤ i ≤ num **范围中的每个数字 **i **，计算其二进制数中的 1 的数目并将它们作为数组返回。
示例 :
输入: 5
输出:[0,1,1,2,1,2]
进阶:
- 给出时间复杂度为O(n×sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？
- 要求算法的空间复杂度为O(n)。
- 你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount）来执行此操作。
思路：动态规划
转自https://leetcode-cn.com/problems/counting-bits/solution/hen-qing-xi-de-si-lu-by-duadua/
dp[i]为i的二进制形式的1的个数
分为两种情况：
1.奇数：二进制表示中，奇数一定比前面那个偶数多一个 1，因为多的就是最低位的 1。
举例：
0 = 0 1 = 1
2 = 10 3 = 11
2.偶数：二进制表示中，偶数中 1 的个数一定和除以 2 之后的那个数一样多。因为最低位是 0，除以 2 就是右移一位，也就是把那个 0 抹掉而已，所以 1 的个数是不变的。
举例：
2 = 10 4 = 100 8 = 1000
3 = 11 6 = 110 12 = 1100
class Solution {
public int[] countBits(int num) {
if(num == 0)
return new int[]{0};
int[] dp = new int[num + 1];//执行用时 :2 ms, 在所有 Java 提交中击败了81.26%的用户
dp[0] = 0;
for(int i = 1; i <= num; i++)
{
if(i % 2 == 1)
{
dp[i] = dp[i-1] + 1;
}
else
{
dp[i] = dp[i/2];
}
}
return dp;
}
}
343. 整数拆分中等
给定一个正整数
n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2，输出: 1，解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: 10，输出: 36，解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
**说明: **你可以假设 *n *不小于 2 且不大于 58。
思路一：动态规划，时间复杂度 O(n2)
定义状态，dp[i] 表示数字 i 拆分为至少两个正整数之和的最大乘积
class Solution {
public int integerBreak(int n) {//执行用时 :1 ms, 在所有 Java 提交中击败了61.04%的用户
int[] dp = new int[n + 1];
dp[2] = 1;
for(int i=3;i<=n;i++){
for(int j=1;j<i;j++){//数字 i 可以拆分成 j + (i - j)
dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
}
}
return dp[n];
}
}
思路二：贪心算法，时间复杂度 O(1)
题目提示You may check the breaking results of n ranging from 7 to 10 to discover the regularities.
应用数学知识分析题目，我们发现当 n>3 时，求 n 除以 3 的整数部分 a 和余数部分 b ，并分为以下三种情况：
当 b = 0 时，直接返回 3a
当 b = 1 时，要将一个 1 + 3 转换为 2+2，因此返回 3a-1 ×4
当 b = 2 时，返回 3a×2
class Solution {
public int integerBreak(int n) {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
if(n <= 3)
return n-1;
int a = n / 3; //a是商
int b = n % 3; //b是余数
if(b == 0){
return (int)(Math.pow(3, a));
}
else if(b == 1){
return (int)(Math.pow(3, a-1) * 4);
}
else{
return (int)(Math.pow(3, a) * 2);
}
}
}
354. 俄罗斯套娃信封问题困难
给定一些标记了宽度和高度的信封，宽度和高度以整数对形式
(w, h)出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
说明:不允许旋转信封。
示例:
输入: envelopes =[[5,4],[6,4],[6,7],[2,3]]
输出: 3
解释: 最多信封的个数为3, 组合为:[2,3] => [5,4] => [6,7]
思路：动态规划+排序
这是LIS问题在二维数组上的扩展，先对宽度 w 进行升序排序，如果遇到 w 相同的情况，则按照高度 h 降序排序。之后把所有的 h 作为一个数组，在这个数组上计算 LIS 的长度。
class Solution {
public int maxEnvelopes(int[][] envelopes) {//执行用时 :188 ms, 在所有 Java 提交中击败57.25%的用户
if(envelopes == null || envelopes.length == 0 || envelopes[0].length == 0)
return 0;
// 按宽度升序排列，如果宽度一样，则按高度降序排列
Arrays.sort(envelopes, new Comparator<int[]>()
{
@Override
public int compare(int[] a, int[] b) {
if(a[0] == b[0]){
return b[1] - a[1];
}else{
return a[0] - b[0];
}
}
});
// 对高度数组寻找 LIS
int[] height = new int[envelopes.length];
for (int i = 0; i < envelopes.length; i++)
height[i] = envelopes[i][1];
return lengthOfLIS(height);
}
public int lengthOfLIS(int[] nums) {
int[] dp = new int[nums.length];
Arrays.fill(dp, 1);//填充dp数组中的每个元素都是1
for(int i=0;i<nums.length;i++){
for(int j=0;j<i;j++){
if(nums[j] < nums[i]){//dp[i]表示以nums[i]结尾的上升子序列的长度
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
int res = 0;
for(int i=0;i<dp.length;i++){
res = Math.max(res, dp[i]);// dp[i] 的最大值是最后要输出的值
}
return res;
}
}
357. 计算各个位数不同的数字个数中等
给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。
示例:
输入: 2
输出: 91
解释: 答案应为除去11,22,33,44,55,66,77,88,99外，在 [0,100) 区间内的所有数字。
思路：动态规划
i=1时，dp[1]=10
i=2时，dp[2]=9×9+dp[1]
i=3时，dp[3]=9×9×8+dp[2]
i=4时，dp[4]=9×9×8×7+dp[3]
dp[i]=(dp[i-1]-dp[i-2])×(10-i+1)+dp[i-1]，dp[i-1]-dp[i-2]是i-1次较i-2次多出来的各位不重复的数字。
class Solution {
public int countNumbersWithUniqueDigits(int n) {//执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 10;
for(int i=2;i<=n;i++){
dp[i] = dp[i-1]+(dp[i-1]-dp[i-2])*(10-i+1);
}
return dp[n];
}
}
363. 矩形区域不超过 K 的最大数值和困难
给定一个非空二维矩阵 matrix和一个整数k，找到这个矩阵内部不大于 k 的最大矩形和。
示例:
输入: matrix = [[1,0,1],[0,-2,3]], k = 2
输出: 2
解释: 矩形区域[[0, 1], [-2, 3]]的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。
说明： 矩阵内的矩形区域面积必须大于 0。如果行数远大于列数，你将如何解答呢？
368. 最大整除子集中等
给出一个由无重复的正整数组成的集合，找出其中最大的整除子集，子集中任意一对 (Si，Sj) 都要满足：Si % Sj = 0 或 Sj % Si = 0。
如果有多个目标子集，返回其中任何一个均可。
示例 1:
输入:[1,2,3]
输出:[1,2](当然,[1,3]也正确)
示例 2:
输入:[1,2,4,8]
输出:[1,2,4,8]
375. 猜数字大小 II中等
我们正在玩一个猜数游戏，游戏规则如下：
我从 1到 n 之间选择一个数字，你来猜我选了哪个数字。
每次你猜错了，我都会告诉你，我选的数字比你的大了或者小了。
然而，当你猜了数字 x 并且猜错了的时候，你需要支付金额为 x 的现金。直到你猜到我选的数字，你才算赢得了这个游戏。
示例:
n = 10, 我选择了8.
第一轮: 你猜我选择的数字是5，我会告诉你，我的数字更大一些，然后你需要支付5块。
第二轮: 你猜是7，我告诉你，我的数字更大一些，你支付7块。
第三轮: 你猜是9，我告诉你，我的数字更小一些，你支付9块。
游戏结束。8 就是我选的数字。
你最终要支付 5 + 7 + 9 = 21 块钱。
给定 n ≥ 1，计算你至少需要拥有多少现金才能确保你能赢得这个游戏。
思路：动态规划
作者：smilyt_
链接：https://leetcode-cn.com/problems/guess-number-higher-or-lower-ii/solution/dong-tai-gui-hua-c-you-tu-jie-by-zhang-xiao-tong-2/
题解看了几遍才能看懂，怀疑自己的脑子已经不转了！！！
class Solution {
public int getMoneyAmount(int n) {//执行用时 :10 ms, 在所有 Java 提交中击败了35.92%的用户
if(n==1)
return 0;
//定义矩阵
int[][] dp = new int[n+1][n+1];
//初始化“\”
for(int i=0;i<=n;i++){
for(int j=0;j<=n;j++){
dp[i][j]=Integer.MAX_VALUE;
}
}
//定义基础值dp[i][i]
for(int i=0;i<=n;i++){
dp[i][i]=0;
}
//按列来，从第2列开始
for(int j=2;j<=n;j++){
//按行来，从下往上
for(int i=j-1;i>=1;i--){
//算除了两端的每一个分割点
for(int k=i+1;k<=j-1;k++){
dp[i][j]=Math.min(k+Math.max(dp[i][k-1],dp[k+1][j]),dp[i][j]);
}
//算两端
dp[i][j]=Math.min(dp[i][j],i+dp[i+1][j]);
dp[i][j]=Math.min(dp[i][j],j+dp[i][j-1]);
}
}
return dp[1][n];
}
}
网友评论