有关网站开发的外文文献,外贸网站需要多少个语言,做一套二级域名网站怎么做,做网站 套模板 后端70. 爬楼梯 #xff08;进阶#xff09;
文章 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬至多m (1 m n)个台阶。你有多少种不同的方法可以爬到楼顶呢#xff1f;
注意#xff1a;给定 n 是一个正整数。
输入描述#xff1a;输入共一行…70. 爬楼梯 进阶
文章 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬至多m (1 m n)个台阶。你有多少种不同的方法可以爬到楼顶呢
注意给定 n 是一个正整数。
输入描述输入共一行包含两个正整数分别表示n, m
输出描述输出一个整数表示爬到楼顶的方法数。
输入示例3 2
输出示例3
提示
当 m 2n 3 时n 3 这表示一共有三个台阶m 2 代表你每次可以爬一个台阶或者两个台阶。
此时你有三种方法可以爬到楼顶。
1 阶 1 阶 1 阶段 1 阶 2 阶 2 阶 1 阶
完全背包问题1-m 物体 weightvalue 背包n 先背包后物品的感知
#include iostream
#include vector
using namespace std;
int main() {int n, m;cin n m;vectorint dp(n 1, 0);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];}}cout dp[n] endl;
}322. 零钱兑换
文章
给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回 -1。
你可以认为每种硬币的数量是无限的。
示例 1
输入coins [1, 2, 5], amount 11 输出3 解释11 5 5 1 示例 2
输入coins [2], amount 3 输出-1 示例 3
输入coins [1], amount 0 输出0 示例 4
输入coins [1], amount 1 输出1 示例 5
输入coins [1], amount 2 输出2 提示
1 coins.length 12 1 coins[i] 2^31 - 1 0 amount 10^4
确认dp数组含义 遍历顺序无所谓因为无论是排序还是组合不影响结果
class Solution {
public:int coinChange(vectorint coins, int amount) {vectorint dp(amount1,10001);dp[0]0;if(amount0) return 0;for(int i0;icoins.size();i){for(int jcoins[i];jamount;j){dp[j]dp[j]dp[j-coins[i]]1?dp[j]:dp[j-coins[i]]1;//coutdp[j] ;}//coutendl;}if(dp[amount]10001) return -1;return dp[amount];}
};279.完全平方数
题目 文章讲解
给定正整数 n找到若干个完全平方数比如 1, 4, 9, 16, …使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
给你一个整数 n 返回和为 n 的完全平方数的 最少数量 。
完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。
示例 1
输入n 12 输出3 解释12 4 4 4 示例 2
输入n 13 输出2 解释13 4 9 提示
1 n 10^4
class Solution {
public:int numSquares(int n) {vectorint dp(n 1, INT_MAX);dp[0] 0;for (int i 0; i n; i) { // 遍历背包for (int j 1; j * j i; j) { // 遍历物品dp[i] min(dp[i - j * j] 1, dp[i]);}}return dp[n];}
};
