爬楼梯（进阶）
70. 爬楼梯
题目：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
示例1：
输入：n = 2 输出：2 解释：有两种方法可以爬到楼顶。 1. 1 阶 + 1 阶 2. 2 阶
首先本题是一个非常简单的 DP 问题，我们可以使用一维的 DP数组 来进行求解，且很快就能解出来。但是，如果我们把题目给换一个下—— 将爬楼梯的方法改为1、2、3、4…这样这个就是完全背包问题，且就可以把方法当作物品，楼梯阶数当作背包容量，且满足上诉的第三类模块—dp[i]+=dp[i-num] 且这个就是一个外循环target和内循环nums。OK，接下来我们来看代码解析。
代码部分
Java版本：
class Solution { public int climbStairs(int n) { int[] dp = new int[n + 1];//定义dp数组 dp[0] = 1;//初始化dp数组，第一个下标值为1 for (int i = 1; i < n + 1; i++){//外循环target从1开始 for (int j = 1 ; j < 3 ; j++){//内循环nums if (i >= j){//判断如果背包容量大于物品重量则计算共有多少种 dp[i] += dp[i - j]; } } } return dp[n]; } }
Python版本：
class Solution: def climbStairs(self, n: int) -> int: dp = [0] * (n + 1) dp[0] = 1 for i in range(1,n + 1): for j in range(1, 3): if i >= j : dp[i] += dp[i - j] return dp[-1]
组合总和IV
377. 组合总和 Ⅳ
题目：
给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。
题目数据保证答案符合 32 位整数范围。
示例：
输入：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) 请注意，顺序不同的序列被视作不同的组合。
思路：
本题一看就是一个 背包问题 ，拿 target当作背包容量，拿nums的元素当作物品。但是这种背包问题是属于上述的那种类型呢？
这个就需要我们仔细去观察了。在题目中我们能通过 组合 这个字眼能知道本题是上述的 组合类型背包 ，所以我们直接套用组合类型的背包模板即可进行一个秒杀。
注意： 和其他背包模板的顺序不同，背包模板的 target 是外循环，且nums 是内循环！！！因为如果两者反过来则会导致一些组合不会被计算上（不要问我怎么知道的5555）。
代码部分
Java版本：
class Solution { public int combinationSum4(int[] nums, int target) { int n = nums.length;//首先获取nums数组的长度。 int[] dp = new int[ target + 1];//创建一个压缩的dp数组（如果不太动压缩的dp数组，可以看参考部分）。 dp[0] = 1;//初始化dp数组。 for (int i = 1; i < target + 1 ; i++){//让target作为外循环。 for (int j = 0 ; j < n ; j++){//让nums作为内循环，且这个一定要是正序（不理解可以去看参考部分） int c = nums[j]; if(i >= c){//进行一个判断，如果背包容量是大于这个物品就需要进行一个累加计算。 dp[i] += dp[i - c]; } } } return dp[target];//返回最后的值。 } }
Python版本：
#道理和Java版本是一样的，这里我就不再过多的赘述了。 class Solution: def combinationSum4(self, nums: List[int], target: int) -> int: dp = [0 for i in range(target + 1)] dp[0] = 1 for i in range(target + 1): for j in nums : if (i >= j): dp[i] +=dp[i - j] return dp[-1]
和本题相似的一个题：322. 零钱兑换大家可以去练习练习！
最后一块石头2
1049. 最后一块石头的重量 II
题目：
有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
如果 x == y，那么两块石头都会被完全粉碎；
如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
来源：力扣（LeetCode）
示例：
输入：stones = [2,7,4,1,8,1] 输出：1 解释： 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]， 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]， 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]， 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
本题相比较于其他题，是一个比较难的一种题，而难点就是在怎么把这个题转化为 背包问题 。其实我们能将石头分为 两 部分，拿其中一部分作为减去另外一部分，则最小的绝对值差值就是我们需要得到的结果，所以我们能拿其中的一部分石头作为 背包容量 ，把stones中的元素作为物品价值，则就可以把本问题转化为了 01背包问题。
代码部分：
Java版本：
class Solution { public int lastStoneWeightII(int[] s) { int Sum = 0;//统计总和 for (int i = 0; i < s.length ; i ++ ){ Sum += s[i]; } int t = Sum / 2;//用sum的一半作为背包容量，也就是说在这个背包能获取的最大子是多少。 int[] dp = new int[t + 1];//创建dp数组。 for(int S = 0 ; S < s.length ; S ++){//进行nums外循环。 for (int j = t ; j >= 0 ; j -- ){//因为是01背包所以需要倒序。 if (j >= s[S]){//判断背包容量是否是大于物品重量。 dp[j] = Math.max(dp[j] , dp[j - s[S]] + s[S]);//套用最大值公式。 } } } return Sum - dp[t] * 2;//减去两倍就相当于最小差值 } }
Python版本：
class Solution: def lastStoneWeightII(self, s: List[int]) -> int: Sum = sum(s) t = Sum // 2 dp = [0 for i in range(t + 1)] for i in s: for j in range(t, 0 , -1): if j >= i: dp[j] = max(dp[j] ,dp[j - i] + i) return Sum - dp[t] * 2
