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]的时候是2
dp[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() 来初始化数组为 7
Arrays.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