代码随想录算法训练营第四十五天 | 279.完全平方数，322. 零钱兑换，70. 爬楼梯 （进阶）

标签：stones 四十五天 进阶 int coins 随想录 ++ amount dp

57. 爬楼梯（第八期模拟笔试） 时间限制：1.000S 空间限制：128MB

题目描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬至多m (1 <= m < n)个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

输入描述

输入共一行，包含两个正整数，分别表示n, m

输出描述

输出一个整数，表示爬到楼顶的方法数。

输入示例

3 2

输出示例

3

提示信息

数据范围：
1 <= m < n <= 32;

当 m = 2，n = 3 时，n = 3 这表示一共有三个台阶，m = 2 代表你每次可以爬一个台阶或者两个台阶。

此时你有三种方法可以爬到楼顶。

 

1. 1 阶 + 1 阶 + 1 阶段
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

---

package main

 

import "fmt"

 

func stair(sky, step int) int { //背包 sky, 石头 1,2,step, 完全背包问题， 排列组合 //dp[i] = 到i阶梯，不同方法 //递推公式 dp[j] = dp[j] + dp[j-step[i]] //初始化 dp[0] //输出 dp := make([]int, sky+1) dp[0] = 1 for j := 0; j < sky+1; j++ { for i := 0; i < step; i++ { if j-i-1 >= 0 { dp[j] = dp[j] + dp[j-i-1] } } } return dp[sky] }

 

func main() { var m, n int fmt.Scan(&m, &n) res := stair(m, n) fmt.Println(res) }

 

---

322. 零钱兑换

  已解答 中等  

相关标签

相关企业  

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

 

示例 1：

输入：

[1, 2, 5]

11

输出：

3

解释：

示例 2：

输入：

[2]

3

输出：

示例 3：

输入：coins = [1], amount = 0
输出：0

 

提示：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 231 - 1
• 0 <= amount <= 104

 

---

func coinChange(coins []int, amount int) int {
    //背包 总金额 amount  石头 钱币 coins 完全背包问题，组合问题  背包容量，amount   石头价格为 -1, 求dp[amount]的最大价格
    //dp[i] 该i容量背包的最大价格
    //递推公式  dp[j] = min(dp[j],dp[i-coins[j]]+1)
    //无限，从左向右遍历
    //输出    dp := make([]int, amount+1)
    for i := 0; i < len(dp); i++ {
        dp[i] = 100000
    }
    dp[0] = 0    for i := 0; i < len(coins); i++ {
        for j := 0; j < amount+1; j++ {
            if j-coins[i] >= 0 && dp[j] > dp[j-coins[i]]+1 {
                dp[j] = dp[j-coins[i]] + 1
            }
        }
    }
    if dp[amount] == 100000 {
        return -1
    }
    return dp[amount]
}

---

279. 完全平方数

  已解答 中等  

相关标签

相关企业  

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

 

示例 1：

输入：

12

输出：解释：

12 = 4 + 4 + 4

示例 2：

输入：

13

输出：解释：

13 = 4 + 9

提示：

• 1 <= n <= 104

 

---

package main import "math" func numSquares(n int) int { //背包 整数n, 石头，1,2,4,9..., 石头价格 1 取背包整数 最小价格， 无限取，完成背包，价值，不是排序，石头先 //dp[i] = i个背包容量，最少数量 //递推 dp[i] = min(dp[i],dp[i-stone[j]]+1) //初始化 dp[0]=0, dp[1~n] = max //输出dp[n] var stones []int for i := 1; i <= 100; i++ { if i*i > n { break } stones = append(stones, i*i) } dp := make([]int, n+1) for i := 1; i < len(dp); i++ { dp[i] = math.MaxInt } for i := 0; i < len(stones); i++ { for j := 0; j < n+1; j++ { if j-stones[i] >= 0 && dp[j-stones[i]] != math.MaxInt && dp[j] > dp[j-stones[i]]+1 { dp[j] = dp[j-stones[i]] + 1 } } } return dp[n] }

标签：stones,四十五天,进阶,int,coins,随想录,++,amount,dp
From： https://www.cnblogs.com/suxinmian/p/18071329