57.爬楼梯
题目：57. 爬楼梯（第八期模拟笔试） (kamacoder.com)
思路：感觉就是套一个公式，for循环要先遍历背包，再遍历物品，因为算的是排列，题目给出的是至多可以爬m个台阶，可以先把m转换为数组，也不对，直接用也行
尝试
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int M = 0;
int N = 0;
N=scanner.nextInt();
M=scanner.nextInt();
int[] dp = new int[N+1];
int[] step = new int[M+1];
for(int i = 1;i<=M; i++){
step[i] = i;
}
dp[0] = 1;
for (int i = 0; i <= N; i++) {
for (int j = 0; j < M; j++) {
if (i >= step[j]) {
dp[i] += dp[i - step[j]];
}
}
}
System.out.print(dp[N]);
}
}
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int M = 0;
int N = 0;
N=scanner.nextInt();
M=scanner.nextInt();
int[] dp = new int[N+1];
dp[0] = 1;
for (int i = 0; i <= N; i++) {
for (int j = 0; j < M; j++) {
if (i >= j) {
dp[i] += dp[i - j];
}
}
}
System.out.print(dp[N]);
}
}
答案
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int M = 0;
int N = 0;
N=scanner.nextInt();
M=scanner.nextInt();
int[] dp = new int[N+1];
dp[0] = 1;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
if (i >= j) {
dp[i] += dp[i - j];
}
}
}
System.out.print(dp[N]);
}
}
小结
- 关键是搞清楚转换为背包问题后，物品遍历的起始位置和终止位置
- 求排列数量，先遍历背包，再遍历物品
- 背包容量大于物品，才能往里面放，所以要有个if 判断
322.零钱兑换
思路：每次凑出来，就计算一次元素总数，这种是在组合的基础上，加上一个要求，求组合最少要有多少个元素，理论上，是要写一个计数的逻辑，一旦符合目标值，就更新计数值，把最小的保留下来，问题在于，要在哪个位置计数，哪个位置更新
尝试（标题4）
class Solution {
public int coinChange(int[] coins, int amount) {
int[] dp = new int[amount+1];
int min = Integer.MAX_VALUE;
int count = 0;
dp[0] = 1;
for(int i = 0; i < amount; i++){
for(int j = 0; j <coins.length; j++){
if(i >= coins[j]){
count++;
dp[i] += dp[i-coins[j]];
}
if(i==amount) min=Math.min(count,min);
}
}
return min;
}
}答案
class Solution {
public int coinChange(int[] coins, int amount) {
int max = Integer.MAX_VALUE;
int[] dp = new int[amount + 1];
//初始化dp数组为最大值
for (int j = 0; j < dp.length; j++) {
dp[j] = max;
}
//当金额为0时需要的硬币数目为0
dp[0] = 0;
for (int i = 0; i < coins.length; i++) {
//正序遍历：完全背包每个硬币可以选择多次
for (int j = coins[i]; j <= amount; j++) {
//只有dp[j-coins[i]]不是初始最大值时，该位才有选择的必要
if (dp[j - coins[i]] != max) {
//选择硬币数目最小的情况
dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
}
}
}
return dp[amount] == max ? -1 : dp[amount];
}
}小结
- for循环从j = coins[i]开始，是为了防止数组下标溢出
- dp[j]：凑足总额为j所需钱币的最少个数为dp[j]
- 凑足总额为j - coins[i]的最少个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] + 1就是dp[j]（考虑coins[i]），所以dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。
- 递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);
【if (dp[j - coins[i]] != max) 】，如果
dp[j - coins[i]]是max，意味着我们还没有找到一种组合来凑成金额j - coins[i]，此时不能用dp[j - coins[i]] + 1来更新dp[j]，因为这将导致无意义的结果。
279.完全平方数
思路：首先，要根据整数n找到小于它的完全平方数，建立物品数组，再去算至少要多少个，跟零钱兑换是一样的，求最少需要多少个元素能够组合出目标值，我需要写一个函数，接受int整数，返回小于该数值的完全平方数构成的int数组
尝试（妈的，终于AC了一次！）
class Solution {
public int numSquares(int n) {
StringBuilder str = new StringBuilder();
for(int i = 1; i <= n; i++) {
if(i * i <= n) {
str.append(i * i).append(","); // 使用逗号分隔
}
}
if (str.length() > 0) {
str.setLength(str.length() - 1); // 移除最后一个逗号
}
String str1 = str.toString();
String[] strArray = str1.split(",");
int[] item = new int[strArray.length];
for (int i = 0; i < strArray.length; i++) {
item[i] = Integer.parseInt(strArray[i]);
}
int[] dp = new int[n+1];
dp[0] = 0;
for(int i = 1;i<n+1; i++){
dp[i] = Integer.MAX_VALUE;
}
for(int i =0; i<=n; i++){
for(int j = 0; j<item.length; j++){
if(i>=item[j]){
dp[i] =Math.min(dp[i],dp[i-item[j]]+1);
}
}
}
return dp[n];
}
}答案
class Solution {
// 版本二， 先遍历背包, 再遍历物品
public int numSquares(int n) {
int max = Integer.MAX_VALUE;
int[] dp = new int[n + 1];
// 初始化
for (int j = 0; j <= n; j++) {
dp[j] = max;
}
// 当和为0时，组合的个数为0
dp[0] = 0;
// 遍历背包
for (int j = 1; j <= n; j++) {
// 遍历物品
for (int i = 1; i * i <= j; i++) {
dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
}
}
return dp[n];
}
}小结
- 想复杂了，物品不需要实现存储在数组里，直接循环的时候，用【int i = 1; i * i <= j;】就能找出来