-
代码随想录算法训练营 动态规划part07
一、爬楼梯 （进阶）
解题思路：
设跳上 n 级台阶有 f(n) 种跳法。在所有跳法中，青蛙的最后一步只有两种情况： 跳上 1 级或 2 级台阶。当为 1 级台阶： 剩 n−1 个台阶，此情况共有 f(n−1) 种跳法。
当为 2 级台阶： 剩 n−2 个台阶，此情况共有 f(n−2)种跳法。
即 f(n)为以上两种情况之和，即 f(n)=f(n−1)+f(n−2) ，以上递推性质为斐波那契数列。因此，本题可转化为 求斐波那契数列的第 n项，区别仅在于初始值不同：青蛙跳台阶问题： f(0)=1 , f(1)=1 , f(2)=2 。
斐波那契数列问题： f(0)=0 , f(1)=1 , f(2)=1 。动态规划解析：
状态定义： 设 dp 为一维数组，其中 dp[i] 的值代表斐波那契数列的第 i 个数字。
转移方程： dp[i+1]=dp[i]+dp[i−1]，即对应数列定义 f(n+1)=f(n)+f(n−1) 。
初始状态： dp[0]=1, dp[1]=1 ，即初始化前两个数字。
返回值： dp[n] ，即斐波那契数列的第 n 个数字。优化：
若新建长度为 n 的 dp 列表，则空间复杂度为 O(N)。
由于 dp 列表第 i 项只与第 i−1 和第 i−2 项有关，因此只需要初始化三个整形变量 sum, a, b ，利用辅助变量 sum 使 a,b 两数字交替前进即可 （具体实现见代码） 。由于省去了 dp 列表空间，因此空间复杂度降至 O(1) 。
- class Solution {
- public int climbStairs(int n) {
- int a = 1, b = 1, sum;
- for(int i = 0; i < n - 1; i++){
- sum = a + b;
- a = b;
- b = sum;
- }
- return b;
- }
- }
二、零钱兑换
- class Solution {
- public int coinChange(int[] coins, int amount) {
- // 自底向上的动态规划
- if(coins.length == 0){
- return -1;
- }
- // memo[n]的值： 表示的凑成总金额为n所需的最少的硬币个数
- int[] memo = new int[amount+1];
- memo[0] = 0;
- for(int i = 1; i <= amount;i++){
- int min = Integer.MAX_VALUE;
- for(int j = 0;j < coins.length;j++){
- if(i - coins[j] >= 0 && memo[i-coins[j]] < min){
- min = memo[i-coins[j]] + 1;
- }
- }
- // memo[i] = (min == Integer.MAX_VALUE ? Integer.MAX_VALUE : min);
- memo[i] = min;
- }
- return memo[amount] == Integer.MAX_VALUE ? -1 : memo[amount];
- }
- }
三、完全平方数
- class Solution {
- public int numSquares(int n) {
- int[] f = new int[n + 1];
- for (int i = 1; i <= n; i++) {
- int minn = Integer.MAX_VALUE;
- for (int j = 1; j * j <= i; j++) {
- minn = Math.min(minn, f[i - j * j]);
- }
- f[i] = minn + 1;
- }
- return f[n];
- }
- }
-
相关阅读:
循环结构 ----- for/in 语句 与 for/of语句
各种小程序/PC/移动端修改代码/文件后, 不热重载问题修复
QT事件介绍
金仓数据库KingbaseES数据库参考手册(服务器配置参数6. 预写式日志)
vue 分页器组件+css动画效果
《第一堂棒球课》：王牌捕手·棒球2号位
企业级自定义表单引擎解决方案（十四）--表单模板2
C#.Net筑基-运算符Family
如何编写难以维护的React代码？耦合组件
前后端分离项目Vue+node.js二手商品交易系统74qb3
- 原文地址：https://blog.csdn.net/m0_63297917/article/details/133177339
