dp第21天

377. 组合总和 Ⅳ

这个参考前面的问题，知道所求的是排列问题，排列的话就要使用背包做外层的遍历。

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

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



 示例 1：

 输入：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：

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


 提示：

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


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

 * @author zeroheart
 *
 */
public class Question377 {

   public int combinationSum4(int[] nums, int target) {
      // 排序不同是不同的组合，那就是排列了。
      int[] dp = new int[target+1];
      int length = nums.length;

      dp[0] = 1;

      for(int i = 0;i<=target; i++){
         for(int j = 0;j<length; j++){
            if(i >= nums[j]){
               dp[i] += dp[i - nums[j]];
            }
         }
      }

      return dp[target];
   }

   public static void main(String args[]){
   }
}

343. 整数拆分

这个是剪绳子问题，我开始以为要自己构造背包问题来做。。。。

/**
 *
 343. 整数拆分
 给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

 返回 你可以获得的最大乘积 。



 示例 1:

 输入: n = 2
 输出: 1
 解释: 2 = 1 + 1, 1 × 1 = 1。
 示例 2:

 输入: n = 10
 输出: 36
 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。


 提示:

 2 <= n <= 58

 * @author zeroheart
 *
 */
public class Question343 {

   public int integerBreak(int n) {
      // 剪绳子问题。。。。我还以为要我自己构建背包呢。。
      //dp[i] 表示 i拆分的最大乘积
      // dp[i] = Max(dp[i],dp[i-j]*j,j*(i-j))

      int[] dp = new int[n+1];
      dp[2] = 1; // 1+1 => 1*1
      for(int i = 3; i<=n; i++){
         for(int j = 1; j<i; j++){
            dp[i] = Math.max(Math.max(dp[i], j * (i-j)), dp[i-j] * j);
         }
      }

      return dp[n];
   }

   public static void main(String args[]){
   }
}

一篇文章吃透背包问题！（细致引入+解题模板+例题分析+代码呈现） – 零钱兑换 – 力扣（LeetCode） (leetcode-cn.com)

279. 完全平方数

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

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



 示例 1：

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

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

 提示：

 1 <= n <= 10^4

 * @author zeroheart
 *
 */
public class Question279 {
   //https://leetcode-cn.com/problems/coin-change/solution/yi-pian-wen-zhang-chi-tou-bei-bao-wen-ti-sq9n/
   public int numSquares(int n) {
      // dp就表示最少值
      int[] dp = new int[n+1];

      Arrays.fill(dp, n+1);
      dp[1] = 1;
      dp[0] = 0;
      for(int i = 1; i<=Math.sqrt(n); i++){
         for(int j = 2; j<=n; j++){
            if(j>=i*i){
               dp[j] = Math.min(dp[j], dp[j - i * i]+1);
            }
         }
      }
      return dp[n];
   }

   public static void main(String args[]){
   }
}