377.动态规划V

给你一个由 不同 整数组成的数组 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

原理

1. 定义状态：
   • 使用一维数组 dp，其中 dp[i] 表示和为 i 的组合数。
   • 例如，dp[target] 就是最终答案，表示和为 target 的组合数。
2. 初始化：
   • dp[0] = 1，表示和为 0 的组合数为 1（即不选任何数字，空组合）。
   • 其他 dp[i] 初始为 0。
3. 状态转移：
   • 对于每个可能的和 i（从 0 到 target），遍历数组 nums 中的每个数字 nums[j]。
   • 如果 i >= nums[j]，说明可以选择 nums[j]，那么和为 i 的组合数可以通过以下方式计算：
     • 在和为 i - nums[j] 的基础上再加上 nums[j]，即可得到和为 i 的组合。
     • 因此，dp[i] += dp[i - nums[j]]。
   • 这样，dp[i] 累加了所有通过选择不同数字 nums[j] 构成和为 i 的组合数。
4. 为什么考虑顺序：
   • 题目要求不同顺序的序列算作不同组合，因此我们在外层循环遍历和 i，内层循环遍历 nums[j]，相当于按照和的递增顺序构建组合，确保了所有可能的排列顺序都被考虑。
   • 例如，对于 nums = [1,2] 和 target = 3，(1,2) 和 (2,1) 是两种不同的组合，因为我们通过动态规划逐步累加所有可能的路径。
5. 时间复杂度：
   • 外层循环：O(target)。
   • 内层循环：O(nums.length)。
   • 总时间复杂度：O(target * nums.length)。
6. 空间复杂度：
   • 使用了大小为 target + 1 的 dp 数组，空间复杂度为 O(target)。

代码

class Solution {
    public int combinationSum4(int[] nums, int target) {
        // 创建动态规划数组，dp[i]表示和为i的组合数
        int[] dp = new int[target + 1];
        
        // 初始状态：和为0的组合数为1（空组合）
        dp[0] = 1;
        
        // 遍历所有可能的和，从0到target
        for (int i = 0; i <= target; i++) {
            // 遍历nums数组中的每个数字
            for (int j = 0; j < nums.length; j++) {
                // 如果当前和i大于等于nums[j]，说明可以用这个数
                if (i >= nums[j]) {
                    // 状态转移：当前和的组合数 += 使用nums[j]后剩余和的组合数
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        
        // 调试用：打印dp数组内容
        for(int i = 0; i <= target; i++) {
            System.out.print(dp[i] + " ");
        }
        
        // 返回目标和的组合数
        return dp[target];
    }
}

57.爬楼梯

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 

每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？ 

注意：给定 n 是一个正整数。

输入描述

输入共一行，包含两个正整数，分别表示n, m

输出描述

输出一个整数，表示爬到楼顶的方法数。

输入示例

3 2

输出示例

3

提示信息

数据范围：
1 <= m < n <= 32;

当 m = 2，n = 3 时，n = 3 这表示一共有三个台阶，m = 2 代表你每次可以爬一个台阶或者两个台阶。

此时你有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶段
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

原理

• 定义状态：
  • 使用一维数组 dp，其中 dp[i] 表示爬到第 i 阶楼梯的方法数。
  • 目标是求 dp[n]，即爬到第 n 阶的方法数。
• 初始化：
  • dp[0] = 1，表示“爬到第0阶”的方法数为1（即不爬，空操作）。
  • 其他 dp[i] 初始为0。
• 状态转移：
  • 对于每一阶 i（从1到n），考虑可以从哪些阶数一步到达 i：
    • 如果可以爬 j 阶（j 从1到 m），且 i >= j，则可以从第 i-j 阶爬 j 阶到达第 i 阶。
    • 因此，dp[i] += dp[i - j]，表示爬到第 i 阶的方法数累加了从第 i-j 阶爬上来的方法数。
  • 通过遍历所有可能的 j（1到m），可以计算出 dp[i]。
• 为什么考虑顺序：
  • 题目要求不同顺序算不同方法。例如，n=3, m=2 的情况，(1,2) 和 (2,1) 是两种不同方法。
  • 动态规划通过累加所有可能的“前一步”状态（dp[i-j]）来确保所有顺序都被覆盖。
• 时间复杂度：
  • 外层循环：O(n)，遍历每层楼梯。
  • 内层循环：O(m)，遍历每次可爬的步数。
  • 总时间复杂度：O(n * m)。
• 空间复杂度：
  • 使用了大小为 n + 1 的 dp 数组，空间复杂度为 O(n)。

代码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 创建Scanner对象读取输入
        Scanner sc = new Scanner(System.in);
        // 读取楼梯总阶数n
        int n = sc.nextInt();
        // 读取每次最多爬的阶数m
        int m = sc.nextInt();
        
        // 创建动态规划数组，dp[i]表示爬到第i阶的方法数
        int[] dp = new int[n + 1];
        
        // 初始状态：爬到第0阶的方法数为1（不爬）
        dp[0] = 1;
        
        // 外层循环：遍历每一阶楼梯（1到n）
        for (int i = 1; i <= n; i++) {
            // 内层循环：尝试每次爬1到m阶
            for (int j = 1; j <= m; j++) {
                // 如果当前阶数i大于等于步数j，可以使用j阶
                if (i >= j) {
                    // 状态转移：爬到i阶的方法数 += 爬到(i-j)阶的方法数
                    dp[i] += dp[i - j];
                }
            }
        }
        
        // 输出爬到第n阶的方法数
        System.out.print(dp[n]);
    }
}

322.零钱兑换

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

原理

• 定义状态：
  • 使用一维数组 dp，其中 dp[i] 表示凑成金额 i 所需的最少硬币数。
  • 目标是求 dp[amount]。
• 初始化：
  • 如果 amount == 0，直接返回 0，因为不需要任何硬币。
  • 初始化 dp 数组：
    • 先只考虑第一种硬币 coins[0]，对于金额 i，如果 i 能被 coins[0] 整除，则 dp[i] = i / coins[0]；否则设为一个极大值（这里用 10001，表示无法凑成）。
    • 选择 10001 作为极大值是因为题目中 amount <= 10^4，而硬币数不会超过这个值（避免溢出）。
• 状态转移：
  • 遍历每种硬币 coins[i]（从第1种开始，因为第0种已用于初始化）。
  • 对于每个金额 j（从 coins[i] 到 amount），考虑是否使用当前硬币：
    • 如果不使用当前硬币，硬币数为 dp[j]。
    • 如果使用当前硬币，硬币数为 dp[j - coins[i]] + 1（即剩余金额 j - coins[i] 的硬币数加1）。
    • 取两者最小值：dp[j] = Math.min(dp[j], 1 + dp[j - coins[i]])。
  • 这样可以逐步更新每个金额的最优解。
• 结果处理：
  • 如果最终 dp[amount] == 10001，说明无法凑成目标金额，返回 -1。
  • 否则，返回 dp[amount]，即最少硬币数。
• 时间复杂度：
  • 初始化循环：O(amount)。
  • 外层循环（硬币种类）：O(coins.length)。
  • 内层循环（金额）：O(amount)。
  • 总时间复杂度：O(coins.length * amount)。
• 空间复杂度：
  • 使用了大小为 amount + 1 的 dp 数组，空间复杂度为 O(amount)。

代码

import java.util.*;

class Solution {
    public int coinChange(int[] coins, int amount) {
        // 如果目标金额为0，直接返回0（不需要硬币）
        if (amount == 0) {
            return 0;
        }
        
        // 创建动态规划数组，dp[i]表示凑成金额i所需的最少硬币数
        int[] dp = new int[amount + 1];
        
        // 初始化dp数组：先考虑只使用第一种硬币（coins[0]）
        for (int i = 0; i <= amount; i++) {
            if (i % coins[0] == 0) {
                // 如果金额i能被coins[0]整除，所需硬币数为i/coins[0]
                dp[i] = i / coins[0];
            } else {
                // 否则设为一个极大值，表示暂时无法凑成该金额
                dp[i] = 10001;
            }
        }
        
        // 遍历剩余的硬币种类
        for (int i = 1; i < coins.length; i++) {
            // 对于每种硬币，从其面额开始遍历到目标金额
            for (int j = coins[i]; j <= amount; j++) {
                // 状态转移：取当前dp[j]和使用当前硬币后的dp[j-coins[i]]+1的最小值
                dp[j] = Math.min(dp[j], 1 + dp[j - coins[i]]);
            }
        }
        
        // 如果dp[amount]仍为初始的极大值，说明无法凑成目标金额，返回-1
        if (dp[amount] == 10001) {
            return -1;
        } else {
            // 否则返回凑成目标金额的最少硬币数
            return dp[amount];
        }
    }
}

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 <= 104

原理

• 定义状态：
  • 使用一维数组 dp，其中 dp[i] 表示和为 i 的最少完全平方数个数。
  • 目标是求 dp[n]。
• 初始化：
  • 对于每个 i（1到n），初始化 dp[i] = i，表示最坏情况下用 i 个1（1是完全平方数）来组成 i。
  • dp[0] 默认是0（无需任何完全平方数）。
  • 计算 nums = floor(sqrt(n))，表示可能用到的最大完全平方数的平方根（例如，n=12 时，nums=3，因为 3^2=9 是最大的可用完全平方数）。
• 状态转移：
  • 遍历所有可能的完全平方数 i^2（i 从2到 nums）。
  • 对于每个完全平方数 i^2，更新从 j = i^2 到 n 的 dp[j]：
    • 如果不使用当前完全平方数 i^2，硬币数为 dp[j]。
    • 如果使用当前完全平方数 i^2，硬币数为 dp[j - i^2] + 1（剩余金额 j - i^2 的硬币数加1）。
    • 取两者最小值：dp[j] = Math.min(dp[j], 1 + dp[j - i^2])。
  • 这样逐步优化每个金额的最少完全平方数个数。
• 时间复杂度：
  • 计算 nums：O(1)。
  • 初始化 dp：O(n)。
  • 外层循环（完全平方数）：O(sqrt(n))。
  • 内层循环（金额）：O(n)。
  • 总时间复杂度：O(n * sqrt(n))。
• 空间复杂度：
  • 使用了大小为 n + 1 的 dp 数组，空间复杂度为 O(n)。

代码

class Solution {
    public int numSquares(int n) {
        // 计算小于等于n的最大完全平方数的平方根，例如n=12时，nums=3（因为3^2=9<=12，4^2=16>12）
        int nums = (int)Math.sqrt((double)n);
        
        // 创建动态规划数组，dp[i]表示和为i的最少完全平方数个数
        int[] dp = new int[n + 1];
        
        // 初始化：dp[i]设为i（最坏情况是用i个1组成）
        for (int i = 1; i <= n; i++) {
            dp[i] = i;
        }
        
        // 遍历所有可能的完全平方数（从2^2到nums^2）
        for (int i = 2; i <= nums; i++) {
            // 对于每个完全平方数i^2，更新从i^2到n的dp值
            for (int j = i * i; j <= n; j++) {
                // 状态转移：取当前dp[j]和使用i^2后的dp[j-i^2]+1的最小值
                dp[j] = Math.min(dp[j], 1 + dp[j - i * i]);
            }
        }
        
        // 返回和为n的最少完全平方数个数
        return dp[n];
    }
}