爬楼梯(第八期模拟笔试)
该题也是昨天的完全背包排列问题,解法相同,将遍历顺序进行调换
java">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的最大值,才能保证在递推公式计算中被覆盖。
- dp[j]代表的是装满容量为j的背包所需的最少硬币数dp[j]
- 递推公式:dp[j]=min(dp[j],dp[j-coins[i]]+1);在这里需要先进行判断,因为dp[j]可能没有被重新计算覆盖,会为最大值,加1会循环到int的最小值加一。若是所有的dp[j]一定能由之前的状态推出的话,就不需要这个判断。
- 初始化:dp[0]=1,其他的都为Integer_MAX_VALUE
- 遍历顺序:这里是求的物品数,先遍历背包和先遍历物品都是一样的,只有求组合数的时候才有区别
java">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];}}
}
完全平方数
这一题和上面一题解法一样,只是要先将完全平方数求出。再进行动规计算
java">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];}
}