代码随想录第三十八天（完全背包问题）|爬楼梯（第八期模拟笔试）|零钱兑换|完全平方数

爬楼梯（第八期模拟笔试）

该题也是昨天的完全背包排列问题，解法相同，将遍历顺序进行调换

import java.util.*;
public class Main{
    public static void main (String[] args) {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int m=sc.nextInt();
        int[] step=new int[m+1];
        for(int i=0;i<m+1;i++){
            step[i]=i;
        }
        maxMethod(n,step);
        
    }
    
    public static void maxMethod(int target,int[] step){
        int[] dp=new int[target+1];
        dp[0]=1;
        for(int j=1;j<target+1;j++){
            for(int i=0;i<step.length;i++){
                if(j>=step[i]){
                    dp[j]+=dp[j-step[i]];
                }
            }
        }
        System.out.println(dp[target]);
    }
}

零钱兑换

这一题也是求放入背包中的物品数，但是不是就放满指定容量背包的最大物品数，而是最小物品数。求最少物品数和最大物品数的区别在于两个地方，一个是递推公式，还有就是初始化，因为要求最小物品数，所以除了dp[0]以外，所有的元素都需要初始化成int的最大值，才能保证在递推公式计算中被覆盖。

1. dp[j]代表的是装满容量为j的背包所需的最少硬币数dp[j]
2. 递推公式：dp[j]=min(dp[j],dp[j-coins[i]]+1);在这里需要先进行判断，因为dp[j]可能没有被重新计算覆盖，会为最大值，加1会循环到int的最小值加一。若是所有的dp[j]一定能由之前的状态推出的话，就不需要这个判断。
3. 初始化：dp[0]=1，其他的都为Integer_MAX_VALUE
4. 遍历顺序：这里是求的物品数，先遍历背包和先遍历物品都是一样的，只有求组合数的时候才有区别

import java.util.*;
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp=new int[amount+1];
        for(int i=1;i<amount+1;i++){
            dp[i]=Integer.MAX_VALUE;
        }
        for(int i=0;i<coins.length;i++){
            for(int j=coins[i];j<amount+1;j++){
                //因为此时初始值都为int的最大值，再加一的话会变成int的最小值+1；所以要判断
                if(dp[j-coins[i]]!=Integer.MAX_VALUE){
                    dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);
                }
            }
        }
        if(dp[amount]==Integer.MAX_VALUE){
            return -1;
        }else{
            return dp[amount];
        }
    }
}

完全平方数

这一题和上面一题解法一样，只是要先将完全平方数求出。再进行动规计算

class Solution {
    public int numSquares(int n) {
        List<Integer> arr=new ArrayList();
        for(int i=0;i<=n;i++){
            double j=Math.sqrt(i);
            if(j%1==0){
                arr.add(i);
            }
        }
        int[] nums=new int[arr.size()];
        for(int i=0;i<nums.length;i++){
            nums[i]=arr.get(i);
        }
        int[] dp=new int[n+1];
        for(int i=1;i<n+1;i++){
            dp[i]=Integer.MAX_VALUE;
        }
        for(int i=0;i<nums.length;i++){
            for(int j=nums[i];j<n+1;j++){
                if(dp[j-nums[i]]!=Integer.MAX_VALUE){
                    dp[j]=Math.min(dp[j],dp[j-nums[i]]+1);
                }
            }
        }
        return dp[n];
    }
}