70.爬楼梯（进阶）

文章：22. 爬楼梯（进阶版）

题目：爬楼梯(kamacoder.com)

【思路】

本题和力扣上面那题不太一样，那题每步只能走1或2步，本题是1<=m<=n，m阶可选。

以及、跨越的阶数是没有数量限制的，因此我们采用完全背包。

1.确认数组及其下标含义

dp[i]：爬到第i阶有dp[i]种方法

2.递推公式

题目求的是爬上n层有多少种方法，也就是求总和

那么递推公式自然是：dp[i]+= dp[i-j]

3.初始化数组

因为递推公式是累加递推，所以我们需要将dp[0]初始化为1，这样后续的累加才有作用。

dp[0]= 1

4.确定遍历顺序

完全背包，且求的是组合数，对物品和背包的遍历顺序没有要求，两个都可以啊。

  • Java实现

woooooo发现java的acm模式不会敲了 ! o !

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.Scanner;
class Main{
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        int m,n ;
        n = sc.nextInt();
        m = sc.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>=0){
                    dp[i] += dp[i-j];
                }
            }
        
        }
        System.out.print(dp[n]);
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package main
import "fmt"
func main(){
    var m,n  int
    fmt.Scan(&n,&m)
    dp:=make([]int,n+1)
    dp[0]=1
    for i:=1;i<=n;i++{
        for j:=1;j <= m;j++{
            if i-j>=0{
                dp[i]+= dp[i-j]
            }
        }
    }
    fmt.Print(dp[n])
}
func max(a,b int)int{
    if a > b{
        return a 
    }
    return b
}

322.零钱兑换

文章：23. 零钱兑换

题目：322. 零钱兑换

【思路】

题目说每种硬币的数量是无限的，也就是说该题是完全背包。

五部曲如下：

1.确定dp数组及其下标的含义

dp[j] : 凑成金额为j的钱币最小个数为dp[j]，钱币的价值为1（values = 1）

2.确定递推公式

凑足总额为j-coins[i]的最小个数为dp[j - coins[i]]，那么只需要加上一个钱币coins[i]即dp[j - coins[i]] +1就是dp[i]，而且需要获取的个数最小：

因此推出递推公式为：dp[j] = min(dp[j] , dp[j-coins[i]] + 1)

3.数组初始化

首先，凑足总金额为0所需的钱币个数一定是0，那么dp[0] = 0

考虑到递推公式的特性，dp[j]必须被初始化为一个最大的数，否则就会在min(dp[j],dp[j-coins[i]]+1)中被初始值覆盖，因此下标非0的元素都应该是最大值。

4.确定遍历顺序

本题求钱币的最小个数，那么钱币的有无顺序都不会影响钱币的最小个数。

也就是都可以！

5.举例推导。。

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int coinChange(int[] coins, int amount) {
        int[]dp = new int[amount+1];
        for(int i =0;i < dp.length;i++){
            dp[i] = Integer.MAX_VALUE-1;
        }
        dp[0]=0;
        for(int i = 0;i < coins.length;i++){
            for(int j = coins[i];j <= amount;j++){
                if( j >= coins[i]){
                    dp[j] = Math.min(dp[j],dp[j-coins[i]]+1);
                }
            }
        }
        return dp[amount] == Integer.MAX_VALUE-1?-1:dp[amount];
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func coinChange(coins []int, amount int) int {
    dp:= make([]int,amount+1)
    for i :=0;i<len(dp);i++{
        dp[i] = math.MaxInt-1
    }
    dp[0] = 0
    for i:=0;i<len(coins);i++{
        for j := coins[i];j<=amount;j++{
            if j>=coins[i]{
                dp[j] = min(dp[j],dp[j-coins[i]]+1)
            }
        }
    }
    if dp[amount] == math.MaxInt-1{
        return -1
    }
    return dp[amount]
}
func min(a,b int)int{
    if a > b{
        return b
    }
    return a
}

279.完全平方数

文章：24. 完全平方数

题目：279. 完全平方数

【思路】

完全平方数是物品（可以无限使用），凑的正整数n就是背包，问凑满这个背包最少需要多少个物品

1.确定dp数组及其下标含义

dp[j]：和为j 的完全平方数的最少数量为dp[j]

2.确定递推公式

dp[j]可以由dp[j - ii]推出，**dp[j] = min(dp[j] , dp[j - i i] +1)

*i i 看作是nums[i]，+1看作是values[i]

3.dp数组如何初始化

dp[0]表示和为0的完全平方数的最小数量，即dp[0] = 0

非零下标：从递推公式中可以看出，我们每次求的都是最小的dp[j]，也就是说我们需要初始化为最大值，避免被初始值覆盖

4.确定遍历顺序

完全背包，求凑满背包需要多少个物品，求的是个数，也就是无论是背包在外循环物品在内循环、还是物品在外循环背包在外循环都是可以的！

5.举例推导。。

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        for(int i = 0;i<dp.length;i++){
            dp[i] = Integer.MAX_VALUE;
        }
        dp[0] = 0;
        for(int i = 1 ; i <=n;i++){
            for(int j = i*i;j <=n;j++){
                dp[j] = Math.min(dp[j],dp[j-i*i]+1);
            }
        }
        return dp[n];
    }
}

  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func numSquares(n int) int {
    dp := make([]int,n+1)
    for i:=0;i<len(dp);i++{
        dp[i] = math.MaxInt
    }
    dp[0]= 0
    for i:=1;i<=n;i++{
        //for j := i;j<=n;j++{ 1更耗时
        for j := i*i;j<=n;j++{ //2更节省时间
            if j >= i*i{ //判断在1有用，2这可忽略
                dp[j] = min(dp[j],dp[j-i*i]+1)
            }
        }
    }
    return dp[n]
}

【算法总结】

  • 爬楼梯：使用完全背包，爬的阶数可以被无限使用。通过累加每一层的阶数得到dp[n]
  • 零钱兑换：使用完全背包，零钱可以被无限使用。通过求dp[j]和dp[j-num[i]]+1的最小值，来获得dp[n]
  • 完全平方数：使用完全背包，完全平方数可以被无限使用。通过求dp[j]和dp[j-i*i]+1的最小值，来获得dp[n]

【语法总结】

  • Java

    1
    2
    3
    4
    //求最大值
    int max = Integer.MAX_VALUE;
    //main函数
    public static void main(String[]args){}

  • Go

    1
    2
    3
    4
    5
    //求最大值
    max:=Math.MaxInt
    //输入
    var m int
    fmt.Scan(&m)