php的网站模板,群晖 wordpress 配置文件,学院网站设计流程,网站建设优化服务精英①、爬楼梯 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢#xff1f; 事例#xff1a; 输入#xff1a;n 2
输出#xff1a;2
解释#xff1a;有两种方法可以爬到楼顶。
1. 1 阶 1 阶
2. 2 阶 思路 事例 输入n 2
输出2
解释有两种方法可以爬到楼顶。
1. 1 阶 1 阶
2. 2 阶 思路 之前用动态规划做过了就是用dp数组保存i个阶梯拥有的方法然后向前累加两个方法数量即可。 进阶使用完全背包思想一次跳一阶两阶可以视为物品由于可以重复使用故使用完全背包。
动态规划 dp定义及含义dp[j]表示跳到第j个阶梯所拥有的方法数。 动态转移方程dp[j] dp[j - i] i为物品(1 / 2) 初始化dp[0] 0 遍历顺序先遍历物品或背包都行使用完全背包思想两个都需要升序遍历 dp[n]即为答案。
代码
public int climbStairs(int n) {//动态规划// if(n 1 || n 2) return n;// int[] dp new int[n 1];// dp[0] 0;// dp[1] 1;// dp[2] 2;// for(int i 3;i n;i){// dp[i] dp[i - 1] dp[i - 2];// }// return dp[n];//完全背包if(n 1 || n 2) return n;int[] dp new int[n 1];int m 2;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];}}return dp[n];}
②、零钱兑换 给你一个整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回 -1 。 你可以认为每种硬币的数量是无限的。 事例 输入coins [1, 2, 5], amount 11
输出3
解释11 5 5 1 思路 使用完全背包思想创建一个dp数组dp[j]表示凑到数额j时所需要的最小硬币个数。由于要求最小值故dp的初始化为dp[0] 0其余为int的最大值。动态转移方程dp[j] Math.min(dp[j],dp[j - coins[i]] 1)由于int的最大值进行加1操作会溢出故得判断j - coins[i]索引下的值是否被替换当替换后才能进行状态转移。
动态规划 dp定义及含义dp[j]表示凑到数额j时所需要的最小硬币个数。 状态转移方程dp[j] Math.min(dp[j],dp[j - coins[i]] 1) 初始化dp[0] 0因为不用凑 其余初始化为int的最大值 遍历顺序物品和背包容量正序遍历两者之间的顺序无要求 dp[amount]若为int的最大值即没法凑到amount 返回-1
代码
public int coinChange(int[] coins, int amount) {if(amount 0) return 0;Arrays.sort(coins);if(amount coins[0]) return -1;int[] dp new int[amount 1];Arrays.fill(dp,Integer.MAX_VALUE);dp[0] 0;for(int i 0;i coins.length;i){for(int j coins[i];j amount;j){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;return dp[amount];}
③、完全平方数 给你一个整数 n 返回 和为 n 的完全平方数的最少数量 。 完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。 事例 输入n 12
输出3
解释12 4 4 4 思路 跟上一题类似只是这题的硬币组合(物品)需要我们自行构造创建一个int数组help大小为sqrt(n)存放从0到sqrt(n)之间的完全平方数。然后使用完全背包思想求得凑到当前数值n的最小个数。
动态规划 dp定义及含义dp[j]表示凑到当前j所使用的最小完全平方数的个数 状态转移方程dp[j] Math.min(dp[j],dp[j - help[i]] 1) 初始化dp[0] 0其余初始化为int的最大值 遍历顺序物品和背包容量正序两者之间无要求 dp[n]即为答案。
代码
public int numSquares(int n) {//构造物品数组 完全平方数数组int[] help new int[(int)(Math.sqrt(n)) 1];int count 0;help[count] 0;for(int i 1;i help.length;i){int num i * i;help[count] num;}int[] dp new int[n 1];Arrays.fill(dp,Integer.MAX_VALUE);dp[0] 0;for(int i 0;i help.length;i){for(int j help[i];j n;j){if(dp[j - help[i]] ! Integer.MAX_VALUE)dp[j] Math.min(dp[j],dp[j - help[i]] 1);}}return dp[n];}
参考代码随想录 (programmercarl.com)
