林重笑

70.爬楼梯（进阶）文章：22. 爬楼梯（进阶版） 题目：爬楼梯(kamacoder.com) 【思路】 本题和力扣上面那题不太一样，那题每步只能走1或2步，本题是1<=m<=n，m阶可选。 以及、跨越的阶数是没有数量限制的，因此我们采用完全背包。 1.确认数组及其下标含义 dp[i]：爬到第i阶有dp[i]种方法 2.递推公式 题目求的是爬上n层有多少种方法，也就是求总和 那么递推公式自然是：dp[i]+= dp[i-j] 3.初始化数组 因为递推公式是累加递推，所以我们需要将dp[0]初始化为1，这样后续的累加才有作用。 dp[0]= 1 4.确定遍历顺序 完全背包，且求的是组合数，对物品和背包的遍历顺序没有要求，两个都可以啊。 Java实现 woooooo发现java的acm模式不会敲了 ! o ! 123456789101112131415161718192021import java.util.Scanner;class Main{ public static void main(String [] ar ...

完全背包理论有N件物品和一个最多能背重量W的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。 完全背包和01背包问题唯一不同的地方就是，每件物品都有无限件。 01背包的背包内嵌循环是从大到小的，是为了保证每一件物品仅被添加一次。 而完全背包的物品是可以添加多次的，所以要从小到大去遍历： 1234567// 先遍历物品，再遍历背包for(int i = 0; i < weight.size(); i++) { // 遍历物品 for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量 dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); }} 1234567/ 先遍历背包，再遍历物品for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量 ...

1049.最后一块石头的重量II文章：14. 最后一块石头的重量II 题目：1049. 最后一块石头的重量 II 【题目】 有一堆石头，每块石头的重量都是正整数。 每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下： 如果 x == y，那么两块石头都会被完全粉碎； 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。 最后，最多只会剩下一块石头。返回此石头最小的可能重量。如果没有石头剩下，就返回 0。 【思路】 本题的题意：尽量将石头分成重量相等的两堆，返回这两堆的差值 1.确认数组及其下标含义 dp[i]：在背包的重量为i时，dp[i]为物品的最大价值（能背的最大重量） 2.确认递推公式 dp[j] = max(dp[j] , dp[j - stone[i]] + stone[i]) 3.数组初始化 题目数值为正整数，非零下标初始化为0即可。 dp[0] = 0 4.确定遍历顺序 因为本题我们使用的是 ...

01背包理论基础01背包01背包：有n件物品和一个最多能背重量为w的背包。第i件物品的重量是weight[i]，得到的价值是values[i]。每件物品只能使用一次，求解将哪些物品装入背包里物品价值总和最大。 二维dp数组01背包1.确定dp数组及其下标含义 对于背包问题，有一种写法：使用二维数组，即dp[i] [j]表示从下标为[0-i]的物品里任意取，放进容量为 j 的背包，价值总和最大是多少。 即i为下标，j为容量。 2.确定递推公式 不放物品：由dp[i-1] [j]推出，里面不放物品i的最大价值，此时dp[i] [j]就是dp[i-1] [j] (就是当物品i的重量大于背包j的重量时，物品i无法放进背包中，所以背包内的价值依然和前面相同。) 放物品i：由dp[i-1] [j-weight[i]]推出，dp[i-1] [j-weight[i]]为背包容量是j-weight[i]的时候不放物品i的最大价值，那么dp[i-1] [j-weight[i] ] + value[i]（物品i的价值），就是背包放物品i得到的最大价值。 所以递归公式： dp[i] [j] = ...

343.整数拆分文章：8. 整数拆分 题目：343. 整数拆分 【思路】 将凑成整数的和，凑出最大的乘积。 1.确定dp[i]及其下标 dp[i] : 拆分数字i，得到的最大乘积dp[i] 2.确定递推公式 dp[i]是如何获得的？ dp[i] 可以 j *(i-j) 、dp[i-1]+1获得。 因此从二者中取最大值即可。 dp[i] = max(j*(i-j) , dp[i-j] *j) 同时，因为i和j 会变化，会重复计算dp[i]，因此我们还需要对dp[i]进行比较 -> dp[i] = max(dp[i],max(dp[i-j]*j, j * (i-j))) 3.数组初始化 dp[2] = 1 4.确定遍历顺序 因为dp[i]依靠dp[i-j]的状态，所以遍历顺序一定是从前向后的。 5.举例推导 。。。。 Java实现 123456789101112class Solution { public int integerBreak(int n) { int[] dp = new int[n+1]; ...

62.不同路径文章：6. 不同路径 题目：62. 不同路径 【思路】 动态规划五部曲： 1.确定dp数组以其下标含义 dp[i] [j]：表示从（0,0）出发，到(i,j)有dp[i] [j]条路径 2.确定递推公式 dp[i] [j]只能从两个方向推导：dp[i-1] [j]/dp[i] [j-1] 因此：dp[i] [j] = dp[i-1] [j] + dp[i] [j-1] 3.数组初始化 dp[0] [0] = 0 dp[1] [0] = 1 dp[0] [1] = 1 4.确定遍历顺序 从上到下，从左到右 Java实现 1234567891011121314151617class Solution { public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; for(int i = 0 ; i < m;i++){ dp[i][0] = 1; ...

动态规划基础理论文章：1. 动态规划理论基础 动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。 动态规划中每一个状态一定是由上一个状态推导出来的，这一点区别于贪心，贪心没有状态推导，而是从局部直接选最优的。 动态规划中dp[i]是由dp[j - weight[i]]推导出来的，然后取max(dp[j],dp[j - weight[i]]+value[i])。 所以贪心解决不了动态规划的问题。 动态规划的解题步骤动态规划五部曲： 1.确定dp数组（dp take）以及下标的含义 2.确定递推公式 3.dp数组如何初始化 4.确定遍历顺序 5.举例推导dp数组 509.斐波那契数文章：2. 斐波那契数 题目：509. 斐波那契数 【思路】 动态规划五部曲： 1.确定dp数组以及下标的含义 dp[i]的含义为：第i个数的斐波那契数值是dp[i] 2.确定递归公式 状态转移方程：dp[i] = dp[i-1] + dp[i-2] 3.dp数组初始化 dp[0] = 0; dp[1] = 1 ...

代码随想录训练营第三十七天 | 单调递增的数字&&*监控二叉树&&贪心总结738.单调递增的数字文章：22. 单调递增的数字 题目：738. 单调递增的数字 【思路】 从后往前遍历，这样可以避开从前往后时出现前一位比后两位的数字小的问题。 332->329->299 循环的起始点是比较倒数第二位（i）和倒数第一位（i-1）的数值 Java实现 123456789101112131415161718class Solution { public int monotoneIncreasingDigits(int n) { //题目给的是数字，我们需要将其转化为一个char数组方便我们对其进行后续的修改。 String s = String.valueOf(n); char[] ch = s.toCharArray(); int start = s.length(); for(int i = s.length()-2;i>=0;i--) ...

代码随想录训练营第三十六天 | 无重叠区间&&划分字母区间&&合并区间435.无重叠区间文章：18. 无重叠区间 题目：435. 无重叠区间 【思路】 左边界排序： 和上一次射箭非常相似，都是先排序，然后通过比较前一个数的右边界是否大于当前数值的左边界来判断她们有没有重叠；没有重叠不做处理，重叠的话就count++、并且更新最右边界（前一数的右边界和当前值的右边界比较）。 相当于删除了重叠靠右的区间。 Java实现 sort函数默认是升序排序，使用lamda表达式是使用了比较器Integer.compare(a[0],b[0])来指定了是使用intervals[0]的值来比较排列 123Arrays.sort(intervals,(a,b)->{ return Integer.compare(a[0],b[0]); }); 123456789101112131415class Solution { public int eraseOverlapIntervals(int[ ...

860.柠檬酸找零文章：13. 柠檬水找零 题目：860. 柠檬水找零 【思路】 有三种情况： 1.账单是5，直接收下 2.账单是10，消耗一个5，增加一个10 3.账单是20，优先消耗一个10和一个5，如果不够，再消耗三个5 分析得出：只有10和5是可以被交易出去的，而10的使用频率比5低。 局部最优：遇到账单20，优先消耗10，完成本次找零。 全局最优：完成全部账单的找零。 Java实现 12345678910111213141516171819202122232425class Solution { public boolean lemonadeChange(int[] bills) { int five = 0; int ten = 0; for(int i : bills){ if(i == 5){ five++; }else if(i == 10){ five- ...