当前位置：首页 > news >正文

【leetcode100】动态规划Java版本

news 来源：原创 2025/9/4 7:14:06

70. 爬楼梯

题目
思考的时候觉得情况很多，无从下手，卡在了找推导公式这一步。
看了随想录后知道以简单的三个阶梯来推导dp公式，为什么不是四个，五个为一组呢？因为题目要求的只能爬1个阶梯，或者2个阶梯，所以从第三个阶梯来思考！（注意看题目）

其他的错误的想法：以为dp[i]=dp[i-1]+1;是不对的，不是阶梯数加一，而是方法数！！！从第i-1到第i个只有dp[i-1]的方法。

错误的：n小于2时会数组越界

class Solution {public int climbStairs(int n) {int [] dp=new int[n+1];dp[1]=1;dp[2]=2; //n小于2时会数组越界for(int i=3;i<n+1;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n];}
}

错误点2：dp[0]=1而不是0,因为dp[2]的时候是2
正确的：

class Solution {public int climbStairs(int n) {int [] dp=new int[n+1];dp[0]=1; //这里得是1,因为dp[2]的时候是2dp[1]=1; for(int i=2;i<n+1;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n];}
}

118.杨辉三角

题目
这一次动态规划公式可以通过找规律想出来，但是不知道怎么对首尾的初始化以及以及每次如何加入到dp数组里。卡在初始化了。

class Solution {public List<List<Integer>> generate(int numRows) {List<List<Integer>> dp=new ArrayList<>(numRows);dp.add(List.of(1));for(int i=1;i<numRows;i++){List<Integer> row=new ArrayList<>(i+1);row.add(1);for(int j=1;j<i;j++) //注意这里是从1开始，i-1结尾，因为首位在循环外添加{row.add(dp.get(i-1).get(j-1)+dp.get(i-1).get(j));}row.add(1);dp.add(row);}return dp;}
}

198.打家劫舍

题目
这道题倒是自己思考出来了，就按着随想录的那五个步骤，心理默默的想每一步，然后把这道题思路和爬楼梯那道题想到一起的，dp【i】的数组就代表的是第i个房子最多打劫多少钱，然后又想到爬楼梯是每次一个或者两个，这里是如果也以三个为最小组的话，就是要么看dp[i-1]大还是dp[i-2]+nums[i]大，也就是第i个是根据前一个的结果或者前两个的结果再跳一个阶梯的结果，看谁更大。

class Solution {public int rob(int[] nums) {if(nums.length==1)return nums[0];int[] dp=new int[nums.length];dp[0]=nums[0];dp[1]=Math.max(nums[0],nums[1]);for(int i=2;i<nums.length;i++){dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);}return dp[nums.length-1];}
}

279.完全平方数

题目
我的思路：
想到的就是第dp[i]表示的是构成它的完全平方数最小的数量，它由前一步dp[i-1]的方法数再加上dp[i-dp[i-1]](这里是错误的想法）的方法数，然后卡住的地方是一个数由完全平方数相加而成的情况很多，不知道如何判断，只能想到遍历但是感觉很奇怪。还写另一个函数来专门判断是否是完全平方数。这一步答案的处理是完全平方数是在[1,根号i]区间内的。
**注意：**一定也要注意i的含义！！
我写的不对的：（没写完）

//不对！！！！！
class Solution {public static boolean isPerfectSquare(int number) {if (number < 0) {return false; // 负数不能开方}// 计算平方根并将其转换为整数double sqrt = Math.sqrt(number);// 判断平方根的整数部分与平方根是否相等return sqrt == (int) sqrt;}public int numSquares(int n) {int[] dp=new int[n+1];dp[1]=1;dp[4]=4;dp[i]=Math.min(dp[i-1]+dp[i-dp[i-1]]);}
}

官方正确答案：

class Solution {public int numSquares(int n) {int[] dp=new int[n+1];  //初始化的意义for(int i=1;i<n+1;i++){int minnum=Integer.MAX_VALUE; for(int j=1;j*j<=i;j++)//不是j<Math.sqrt(i) ，这一步就是看的是sqrt(i)有多少种方法，然后后面dp[i]=minnum+1就是相当于把sqrt(i)平方了{minnum=Math.min(minnum,dp[i-j*j]); //用减的形式表示和}dp[i]=minnum+1;}return dp[n];}
}

其他知识点：
Integer.MIN_VALUE: 表示 int 类型的最小值。
Long.MIN_VALUE: 表示 long 类型的最小值。
Double.MIN_VALUE: 表示 double 类型的最小正值。
Float.MIN_VALUE: 表示 float 类型的最小正值。
对于浮点类型的最小值，你还可以使用 Double.NEGATIVE_INFINITY 和 Float.NEGATIVE_INFINITY 来表示负无穷大。

322.零钱兑换

题目
没有思路，还是没有推导出来动态规划公式。这里的技巧：

初始化：不是默认设置为0，而是为amount+1
Arrays.fill(dp,amount+1);//这里是每一个值都比amount大1,是为了标记有没有这个答案，即使中间的没有，那么最终的结果dp[amount]会比amount大的
有了1之后，动态规划公式的比较就是比较dp[i]和dp[i-coins[j]+1哪个更小了，如果是默认为0，就不能比较了。注意这个+1和上面题目完全平方数是一样的。

官方答案：

class Solution {public int coinChange(int[] coins, int amount) {int[] dp=new int[amount+1]; Arrays.fill(dp,amount+1);dp[0]=0;for(int i=1;i<amount+1;i++){int mincoin=Integer.MIN_VALUE;for(int j=0;j<coins.length;j++){if(coins[j]<=i)//肯定比i小{dp[i]=Math.min(dp[i],dp[i-coins[j]]+1); //要么没有也就是dp[i]（这里肯定就比amount大），要么是第i的数减去coins[j]加一（也就是加的coins[j]的值这一项）}}}return dp[amount]>amount?-1:dp[amount];}
}

其他：
数组初始化：

int[] dp=new int[amount+1]; 
Arrays.fill(dp,amount+1);

Java8之后可以用Arrays.setAll()

int[] arr = new int[5];// 使用 Arrays.setAll() 来初始化数组为 7Arrays.setAll(arr, i -> 7);

二维数组：

        int[][] arr = new int[3][3];        // 使用 Arrays.fill() 填充每一行for (int i = 0; i < arr.length; i++) {Arrays.fill(arr[i], 7);}

300.最长递增子序列

题目
没有思路，看了答案，感觉这种题目都是先考虑前一项（像爬楼梯）即dp[i-1]或者[0…dp[j]] j<i 这种来递推，考虑的时候会假设前面的那些已经求好了，有点像数学归纳法，假设第k-1项符合，然后证明第k项。

class Solution {public int lengthOfLIS(int[] nums) {if(nums.length==0)return 0;int[] dp=new int[nums.length];Arrays.fill(dp,1);int maxnum=1; //而不是Integer.MIN_VALUE//  dp[0]=1;for(int i=1;i<nums.length;i++){for(int j=0;j<i;j++){if(nums[j]<nums[i]){dp[i]=Math.max(dp[i],dp[j]+1);}}maxnum=Math.max(dp[i],maxnum);              }return maxnum;}
}

139.单词拆分

题目

152.乘积最大子数组

题目
思路错误：

错误的：

dp[i]=Math.max(dp[i-1],dp[i-1]*nums[i]); //要连续，所以不对

2.错误的：只要变小就要从这个小的从头开始计算最大的连续值
又想的是要连续的话，如果后一个和前一个相乘结果变小了，那就段了，从dp[i]从头开始了，先把用nums数组初始化dp，dp[i]表示的就是i前面最大的连续乘积，但是这种方法也不对，比如例子：【-2，3，-4】我的输出就是3，而正确结果是24，错误原因：我相当于把nums整个数组分割成每一个小段了，只比较了的dp[i-1]*nums[i]和dp[i-1],相当于只考虑了前一个数字，没有整个考虑。
【看官网原因更清晰】

//错误的！！！
class Solution {public int maxProduct(int[] nums) {int[] dp=Arrays.copyOf(nums,nums.length);int maxnum=nums[0];for(int i=1;i<nums.length;i++){if(dp[i-1]*nums[i]>dp[i-1]){dp[i]=dp[i-1]*nums[i];}}for(int i=1;i<nums.length;i++){maxnum=Math.max(maxnum,dp[i]);}return maxnum;}
}

乘了nums[i]可能变大也可能变小，如果是负数的话想让负数更多，如果是正数的话想让正数更多，所以维护两个数组，分别看最大的数组和最小的数组乘了nums[i]后，谁更大，为什么和nums[i]也要比较呢？

  int[] maxdp=int [nums.length];maxdp[0]=nums[0];mindp[0]=nums[0];for(int i=1;i<nums.length;i++){maxdp=Math.max(Math.max(maxdp[i-1]*nums[i],mindp[i-1]*nums[i]),nums[i]);//要从nums[i]开始重新计算连续的mindp=Math.min(Math.min(maxdp[i-1]*nums[i],mindp[i-1]*nums[i]),nums[i]);}return