贪心+动归1

​​​​​​​​​​​​​​跳跃游戏

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

class Solution {public boolean canJump(int[] nums) {// 跳跃覆盖范围究竟可不可以覆盖到终点！// 直接取最大值，总和大于nums.length即可if (nums.length == 1) {return true;}// 覆盖范围, 初始覆盖范围应该是0，因为下面的迭代是从下标0开始的int cover = 0;// 在覆盖范围内更新最大的覆盖范围 因此是i<=coverfor (int i = 0; i <= cover; i++) {cover = Math.max(cover, i + nums[i]); // 直接在当前下标加上能跳的最大范围if (cover >= nums.length - 1) {return true;}}return false;}
}

跳跃游戏 II

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

• 0 <= j <= nums[i]
• i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

class Solution {public int jump(int[] nums) {//要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最少步数！//在数组末端时，不需要跳转 步数为0if (nums == null || nums.length == 0 || nums.length == 1) {return 0;}//需要统计两个覆盖范围，当前这一步的最大覆盖和下一步最大覆盖。//记录跳跃的次数int count = 0;//当前的覆盖最大区域int curDistance = 0;//最大的覆盖区域int maxDistance = 0;for (int i = 0; i < nums.length; i++) {//在可覆盖区域内更新最大的覆盖区域maxDistance = Math.max(maxDistance, i + nums[i]);//说明当前一步，再跳一步就到达了末尾if (maxDistance >= nums.length - 1) {count++;break;}//走到当前覆盖的最大区域时，更新下一步可达的最大区域if (i == curDistance) {curDistance = maxDistance;count++;}}return count;}
}

划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

edge[chars[i] - 'a'] = i; 找到i对应位置 找到i对应位置 例如：字母c edge[2]=i;进行更新，找到最后位置

class Solution {public List<Integer> partitionLabels(String s) {//如何统计相同字母出现的最大下标：统计次数//1.统计每一个字符最后出现的位置//2.从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点List<Integer> list = new LinkedList<>();int[] edge = new int[27];char[] chars = s.toCharArray();//1.统计每一个字符最后出现的位置for (int i = 0; i < chars.length; i++) {edge[chars[i] - 'a'] = i;  //eg.  字母c edge[2]=i;进行更新，找到最后位置}//2.从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点int left = 0;//为什么取-1int right = 0;for (int i = 0; i < chars.length; i++) {right = Math.max(right, edge[chars[i] - 'a']);//获取字符最远处下标if (i == right) {list.add(right - left + 1);//统计本次符合条件个数left = i + 1;}}return list;}
}

无重叠区间

重叠区间问题

给定一个区间的集合 intervals ，其中 intervals[i] = [start(i), end(i)] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

class Solution {public int eraseOverlapIntervals(int[][] intervals) {/*重叠区间问题//1.按照左区间或是右区间进行排序//2.比较intervals[i][0]和interval[i-1][1](左边界和右边界)//3.更新最小右边界//根据题目要求：合并 、删除 。。。*///1.按照左区间或是右区间进行排序Arrays.sort(intervals, (a, b) -> {//升序排列return Integer.compare(a[0], b[0]);});//2.比较intervals[i][0]和interval[i-1][1](左边界和右边界)int remove = 0;//需要移除的区间数。int pre = intervals[0][1];//初始化为第一个区间的结束位置 intervals[0][1]。for (int i = 1; i < intervals.length; i++) {//3.更新最小右边界 上一个区间右边界与下一个区间左边界比较if (pre > intervals[i][0]) {//检查当前区间的起始位置 intervals[i][0] 是否小于前一个区间的结束位置 pre。remove++;pre = Math.min(pre, intervals[i][1]);//更新 pre 为当前区间结束位置 intervals[i][1] 和 pre 的较小值，以确保下一个区间的起始位置不小于 pre。} else {pre = intervals[i][1];}}return remove;}
}

动态规划（重叠子问题）

动态规划问题的一般形式就是求最值。比如说让你求最长递增子序列呀，最小编辑距离呀等等。

如果某一问题有很多重叠子问题，使用动态规划是最有效的。动态规划中每一个状态一定是由上一个状态推导出来的。

动规是由前一个状态推导出来的，而贪心是局部直接选最优的。

明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。

重叠子问题、最优子结构、状态转移方程就是动态规划三要素

递归算法的时间复杂度怎么计算？就是用子问题个数乘以解决一个子问题需要的时间。

动态规划的解题步骤

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化 （递推公式决定了dp数组要如何初始化）
4. 确定遍历顺序
5. 举例推导dp数组

斐波那契数

「自底向上」的思路：直接从最底下、最简单、问题规模最小、已知结果的 f(1) 和 f(2)（base case）开始往上推，直到推到我们想要的答案 f(20)。这就是「递推」的思路，这也是动态规划一般都脱离了递归，而是由循环迭代完成计算的原因。

class Solution {public int fib(int n) {if(n<=1){return n;}//dp[i]的定义为：第i个数的斐波那契数值是dp[i]int[]dp=new int[n+1];dp[0]=0;dp[1]=1;for(int i=2;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n];}
}

70 爬楼梯

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

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

class Solution {public int climbStairs(int n) {//dp[i]： 爬到第i层楼梯，有dp[i]种方法int[] dp = new int[n + 1];  //为了存储第0层到第n层的结果 数组长度是n+1
0       dp[0]=1;dp[1]=1;for(int i=2;i<=n;i++){dp[i] = dp[i - 1] + dp[i - 2];}return dp[n];}
}

使用最小花费爬楼梯

class Solution {public int minCostClimbingStairs(int[] cost) {//dp[i]的定义：到达第i台阶所花费的最少体力为dp[i]。int[] dp = new int[cost.length+1];//前两台阶不费力dp[0] = 0;dp[1] = 0;//最小花费，递推公式和花费联系上for(int i=2;i<=cost.length;i++){dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);}return dp[cost.length];}}

118 杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

class Solution {public List<List<Integer>> generate(int numRows) {// 结果集合List<List<Integer>> res = new ArrayList<>();// 行for (int i = 0; i < numRows; i++) {// 每一行List<Integer> list = new ArrayList<>();// 行数等于列数int row = i + 1; //列数for (int j = 0; j < row; j++) {//如果当前列是第一列或最后一列，则将 1 添加到当前行的列表中if (j == 0 || j == row - 1) {list.add(1);} else {//否则，使用上一行的第 j 列和第 j-1 列的值相加，将结果添加到当前行的列表中。//获取上一行数据List<Integer> pre = res.get(i - 1);int num = pre.get(j) + pre.get(j - 1);list.add(num);}}res.add(list);}return res;}
}

背包问题

背包问题，大家都知道，有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

背包问题有多种背包方式，常见的有：01背包、完全背包、多重背包、分组背包和混合背包等等。

要注意题目描述中商品是不是可以重复放入。

即一个商品如果可以重复多次放入是完全背包，而只能放入一次是01背包，写法还是不一样的。

问能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); ，对应题目如下：

416.分割等和子集 (物品正序，背包倒序)

给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

---

这道题目就是一道01背包应用类的题目，需要我们拆解题目，然后套入01背包的场景。

01背包相对于本题，主要要理解，题目中物品是nums[i]，重量是nums[i]，价值也是nums[i]，背包体积是sum/2。

class Solution {public boolean canPartition(int[] nums) {/*** 1. 确定dp数组及下标含义 ：容量为j的背包，所背的物品价值最大可以为dp[j]，背包价值等于总和的一半* 2. 递推公式 dp[j]=Math.max(dp[j],dp(j-nums[i])+nums[i])* 3. 初始化 dp[0]=0 非零dp[]:0 只包含正整数的非空数组，所以非0下标的元素初始化为0* 4. 遍历顺序 dp[j] 如果使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！* 5. 推导结果*/if (nums == null || nums.length == 0) {return false;}int sum = 0;for (int num : nums) {sum += num;}//总和为奇数不能平分if (sum % 2 != 0) {return false;}int target = sum / 2;int[] dp = new int[target + 1];for (int i = 0; i < nums.length; i++) {//物品for (int j = target; j >= nums[i]; j--) {//背包 倒序遍历dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);}//剪枝一下，每一次完成for-loop，立即检查是否dp[target] == targetif (dp[target] == target) {return true;}}return dp[target] == target;}
}

• 动态规划：1049.最后一块石头的重量 II(opens new window)

问装满背包有几种方法：dp[j] += dp[j - nums[i]] ，对应题目如下：

• 动态规划：494.目标和(opens new window)

518. 零钱兑换 II(opens new window)

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

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。

---

/*** 先物品后背包的情况下，根据递推公式，dp【j】一定是来自于外层上一次的结果，而外层上一次的结果一定是来源于上一个物品的dp数组，所以不会出现物品2在物品1之前的情况，也就是只会出现【物品1，物品1，物品2】这种情况，而物品2不会出现在物品1之前，（不会重复）恰好对应组合问题；* 而外层遍历背包 内层遍历物品就不一样了，每一层的dp【j】都是在固定j的情况下，把物品从头开始遍历，所以dp【j】来自于上一层的结果，而上一层的结果又遍历了所有物品，所以这种遍历方式会出现【物品1，物品2，物品1】这种情况，恰好对应了排列问题* 组合不强调元素之间的顺序，排列强调元素之间的顺序。* * 1.dp[j]：凑成总金额j的货币组合数为dp[j]* 2.dp[j] 就是所有的dp[j - coins[i]]（考虑coins[i]的情况）相加。* dp[j] += dp[j - coins[i]];* 3.初始化  dp[0] = 1 下标非0的dp[j]初始化为0，这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]* 4.遍历顺序 先物品后背包* 如果求组合数就是外层for循环遍历物品，内层for遍历背包。* 如果求排列数就是外层for遍历背包，内层for循环遍历物品。*/
class Solution {public int change(int amount, int[] coins) {int[] dp = new int[amount + 1];dp[0]=1;//判断条件决定遍历的背包还是物体  求的是组合数for (int i = 0; i <coins.length; i++) {//物品   for (int j = coins[i]; j <=amount ; j++) {//背包  价值到背包dp[j]+=dp[j-coins[i]];}}return dp[amount];}
}