做淘宝导航网站新媒体培训

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

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

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];}
}