重庆网站制作1000,网络营销推广的心得体会,郑州互联网seo使用教程,建设网站的网络公司70. 爬楼梯 #xff08;进阶#xff09; 题目描述#xff1a; 假设你正在爬楼梯。需要 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 阶 确定dp数组以及下标的含义 dp[i]爬到有i个台阶的楼顶有dp[i]种方法。 确定递推公式 在动态规划494.目标和 (opens new window)、 动态规划518.零钱兑换II (opens new window)、动态规划377. 组合总和 Ⅳ (opens new window)中我们都讲过了求装满背包有几种方法递推公式一般都是dp[i] dp[i - nums[j]]; 本题呢dp[i]有几种来源dp[i - 1]dp[i - 2]dp[i - 3] 等等即dp[i - j] 那么递推公式为dp[i] dp[i - j] dp数组如何初始化 既然递归公式是 dp[i] dp[i - j]那么dp[0] 一定为1dp[0]是递归中一切数值的基础所在如果dp[0]是0的话其他数值都是0了。 下标非0的dp[i]初始化为0因为dp[i]是靠dp[i-j]累计上来的dp[i]本身为0这样才不会影响结果 确定遍历顺序 这是背包里求排列问题即1、2 步 和 2、1 步都是上三个台阶但是这两种方法不一样 所以需将target放在外循环将nums放在内循环。 每一步可以走多次这是完全背包内循环需要从前向后遍历。 举例来推导dp数组
import java.util.Scanner;public class Main{public static void main(String[] args){Scanner innew Scanner(System.in);int nin.nextInt();int min.nextInt();int[] dpnew int[n1];dp[0]1;for(int j1;jn;j){for(int i0;im;i){if(ji){dp[j]dp[j]dp[j-i];}}}System.out.println(dp[n]);}
}
时间复杂度Omn 空间复杂度On
322. 零钱兑换 动规五部曲分析如下 确定dp数组以及下标的含义 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]); dp数组如何初始化 首先凑足总金额为0所需钱币的个数一定是0那么dp[0] 0; 其他下标对应的数值呢 考虑到递推公式的特性dp[j]必须初始化为一个最大的数否则就会在min(dp[j - coins[i]] 1, dp[j])比较的过程中被初始值覆盖。 所以下标非0的元素都是应该是最大值。 确定遍历顺序 本题求钱币最小个数那么钱币有顺序和没有顺序都可以都不影响钱币的最小个数。 所以本题并不强调集合是组合还是排列。 综上所述遍历顺序为coins物品放在外循环target背包在内循环。且内循环正序。 举例推导dp数组
class Solution {public int coinChange(int[] coins, int amount) {int maxInteger.MAX_VALUE;int[] dpnew int[amount1];for(int i0;idp.length;i){dp[i]max;}dp[0]0;for(int i0;icoins.length;i){for(int jcoins[i];jamount;j){if(dp[j-coins[i]]!max){//只有dp[j-coins[i]]不是初始最大值时该位才有选择的必要dp[j]Math.min(dp[j],dp[j-coins[i]]1);}}}return dp[amount]max?-1:dp[amount];}
}时间复杂度: O(n * amount)其中 n 为 coins 的长度 空间复杂度: O(amount)
279.完全平方数 动规五部曲分析如下 确定dp数组dp table以及下标的含义 dp[j]和为j的完全平方数的最少数量为dp[j] 确定递推公式 dp[j] 可以由dp[j - i * i]推出 dp[j - i * i] 1 便可以凑成dp[j]。 此时我们要选择最小的dp[j]所以递推公式dp[j] min(dp[j - i * i] 1, dp[j]); dp数组如何初始化 dp[0]表示 和为0的完全平方数的最小数量那么dp[0]一定是0。 有同学问题那0 * 0 也算是一种啊为啥dp[0] 就是 0呢 看题目描述找到若干个完全平方数比如 1, 4, 9, 16, …题目描述中可没说要从0开始dp[0]0完全是为了递推公式。 非0下标的dp[j]应该是多少呢 从递归公式dp[j] min(dp[j - i * i] 1, dp[j]);中可以看出每次dp[j]都要选最小的所以非0下标的dp[j]一定要初始为最大值这样dp[j]在递推的时候才不会被初始值覆盖。 确定遍历顺序 我们知道这是完全背包 如果求组合数就是外层for循环遍历物品内层for遍历背包。 如果求排列数就是外层for遍历背包内层for循环遍历物品。
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;}dp[0]0;for(int i1;i*in;i){int weighti*i;for(int jweight;jn;j){dp[j]Math.min(dp[j],dp[j-weight]1);}}return dp[n];}
}时间复杂度: O(n * √n) 空间复杂度: O(n)
