377 组合总和Ⅱ

题目

给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

题目数据保证答案符合 32 位整数范围。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：

1
2
输入：nums = [9], target = 3
输出：0

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 1000
  • nums 中的所有元素 互不相同
  • 1 <= target <= 1000

进阶：如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？

思路

题目中说到：从 nums 中找出并返回总和为 target 的元素组合的个数。 但是后面又紧跟着说顺序不同的作为不同的组合。 那么本题就不能看成单纯的组合数 ，而是排列。因为排列对于顺序有要求， 所以需要按照排列的思维去思考同时还需要有动态规划的思考。 这就是这道题难的地方。

按照动规的思路dp[i] : 表示总和为i的组合的个数为dp[i]

还有需要注意的就是遍历的顺序， 一般来说对于背包问题：

**求组合是外层遍历物品，内层遍历背包。 **

求排列是外层遍历背包，内层遍历物品。

所以，本题我们也是采用这种遍历方式进行。

实现

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 combinationSum4(int[] nums, int target) {

        //如果求组合数就是外层for循环遍历物品，内层for遍历背包。
        // 如果求排列数就是外层for遍历背包，内层for循环遍历物品。

        int []dp = new int[target+1];
        dp[0] = 1;
        //外层遍历背包
        for(int j = 0; j <= target;j++){
           	//内层遍历物品
            for(int i =0 ;i < nums.length;i++){
                //如果被当前背包的容量 >= 物品的重量， 那么就进行递推。 否则就遍历下一个数
                if( j >= nums[i] ){
                    //求组合数使用 += 求最大值/最小值 使用max/min
                    dp[j] += dp[j-nums[i]];
                }
            }
        }
        return dp[target];
    }
}

322 零钱总换

题目

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

示例 1：

1
2
3
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

1
2
输入：coins = [2], amount = 3
输出：-1

示例 3：

1
2
输入：coins = [1], amount = 0
输出：0

提示：

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 231 - 1
  • 0 <= amount <= 104

思路

本题和我们之前做的零钱总换(地址: https://wclspace.xyz/post/4ee41ff3.html#518-%E9%9B%B6%E9%92%B1%E6%80%BB%E6%8D%A2)是一个类型的题， 上一道这个题是要求返回凑成总金额的组合数， 而本题是返回可以凑成总金额所需的最少的硬币个数 所以这两道题在递推公式上略有不同。

dp[i]:表示 可以凑成总金额 i 所需的 最少的硬币个数为dp[i]

这道题对于遍历的位次顺序要求就没那么高了， 先遍历背包或者物品都行 ，这里我用先遍历物品（习惯）。同时， 因为对于数组中的银币的数量是无限制的， 所以我们可以一直使用同一个， 所以在内层遍历背包的时候需要正序遍历， 这样就可以保证同一个硬币被多次使用了。

注意： 因为要获取最少的硬币个数 ，所以在初始化dp数组的时候需要将其赋予最大值， 这样才能再每次递推的时候获取最小值（也就是最少使用硬币个数）

对于dp[0]的初始化，这里给dp[0] = 0，按照题意总金额为 0的个数也是 0 。 所以可以赋值为0 ， 至于其他的， 我们需要赋值为最大值 ，原因上面有说

实现

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 coinChange(int[] coins, int amount) {
        //题目要求 : 返回可以凑成总金额所需的 最少的硬币个数     
        int []dp = new int[amount +1];
        //dp[i] 表示 凑成总金额为i所需要的最少硬币数为 dp[i]

        //需要计算最大的硬币面值
        for(int i = 0;i < dp.length; i++){
            dp[i] = Integer.MAX_VALUE;
        }
        //初始化dp[0] = 0 if amount == 0 then dp[0] = 0
        dp[0] = 0;
        for(int i =0 ;i < coins.length;i++){
            for(int j = coins[i]; j <= amount;j++){
                if(dp[j-coins[i]] != Integer.MAX_VALUE){
                    dp[j] = Math.min(dp[j], dp[j-coins[i]] +1);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

279 完全平方数

题目

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

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

示例 1：

1
2
3
输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：

1
2
3
输入：n = 13
输出：2
解释：13 = 4 + 9

提示：

  • 1 <= n <= 104

思路

题中要求: 返回和为 n的完全平方数的最少数量

所以**dp[i]: 可以表示 和为 i 的完全平方数的最少数量是dp[i]**

遍历顺序还是使用先物品 后背包的方式， 如果物品的重量 > 背包的容量。 那么就直接continue， 否则就进行递推公式

1
2
3
for(int i= 1; i*i <= n; i++){
    for(int j = i*i; j<= n; j++)
}

因为本题需要的是最数量， 所以我们在初始化dp[i]的时候， 需要将其赋值为MAX_VALUE， 这样才能实现min(dp[j],dp[j-i*i] + 1)的时候取最小值。 同时对于dp[0] =0 因为 和为 0 的完全平方数最少数量本来就是 0

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int numSquares(int n) {
        int []dp = new int[n+1];
        //dp[i]： dp数组的含义是 和为整数i的 完全平方数最少数量为dp[i]
    
        for(int i =0 ;i <= n; i++){
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = 0;

        for(int i = 1; i*i <= n;i++){
            for(int j = i*i; j <= n;j++){
                dp[j] = Math.min(dp[j], dp[j- i*i]+1);
            }
        }
        return dp[n];

    }
}

139 单词拆分

题目

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 1：

1
2
3
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2：

1
2
3
4
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
     注意，你可以重复使用字典中的单词。

示例 3：

1
2
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

提示：

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s 和 wordDict[i] 仅由小写英文字母组成
  • wordDict 中的所有字符串 互不相同

思路

二刷fail

因为题目中混合字符串， 所以一时没有想出来字符串的拆分和dp[]数组怎么建立联系， 如何知道s中是否含有wordDict的内容， 刚开始想到的是用集合来contains判断， 但是这样会导致时间复杂度极高， 比暴力还爆力，根本不可行，所以就没有ac下来。

先不考虑如何判断s中是否存在wordDict中的词， 先按照动态规划的思路将这道题理顺。

既然是看 wordDict是否在s中， 那么就把s看作背包， 看wordDict中的内容能否将其装满， 能那就返回true ，不能就是false ，暂时就这么简单的思考。

接下来按照动规五部曲。 dp[i] ：字符串长度为i， dp[i] = true，表示可以拆分为一个或多个在字典中出现的单词。

初始化dp[0] = true 。因为dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递推的根基，dp[0]一定要为true，否则递推下去后面都都是false了。

实现

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 str: wordDict){
                int len = str.length();
                //判断是否满足条件
                //1. len<=i 
                //2. s.substring(i-len, i) == str 
                //3. dp的递推公式中的dp[i-len] == true ，需要判断上一个循环是否满足条件
                if(i>= len && dp[i-len] && str.equals(s.substring(i-len,i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }
}