• 代码随想录算法训练营 动态规划part07

    一、爬楼梯 （进阶）

    70. 爬楼梯 - 力扣（LeetCode）

    解题思路：
    设跳上 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) 。

    1. class Solution {
    2.     public int climbStairs(int n) {
    3.         int a = 1, b = 1, sum;
    4.         for(int i = 0; i < n - 1; i++){
    5.             sum = a + b;
    6.             a = b;
    7.             b = sum;
    8.         }
    9.         return b;
    10.     }
    11. }
    12.

    二、零钱兑换 

    322. 零钱兑换 - 力扣（LeetCode）

    1. class Solution {
    2.     public int coinChange(int[] coins, int amount) {
    3.         // 自底向上的动态规划
    4.         if(coins.length == 0){
    5.             return -1;
    6.         }
    7.  
    8.         // memo[n]的值： 表示的凑成总金额为n所需的最少的硬币个数
    9.         int[] memo = new int[amount+1];
    10.         memo[0] = 0;
    11.         for(int i = 1; i <= amount;i++){
    12.             int min = Integer.MAX_VALUE;
    13.             for(int j = 0;j < coins.length;j++){
    14.                 if(i - coins[j] >= 0 && memo[i-coins[j]] < min){
    15.                     min = memo[i-coins[j]] + 1;
    16.                 }
    17.             }
    18.             // memo[i] = (min == Integer.MAX_VALUE ? Integer.MAX_VALUE : min);
    19.             memo[i] = min;
    20.         }
    21.  
    22.         return memo[amount] == Integer.MAX_VALUE ? -1 : memo[amount];
    23.     }
    24. }
    25.

    三、完全平方数 

    279. 完全平方数 - 力扣（LeetCode）

    1. class Solution {
    2.     public int numSquares(int n) {
    3.         int[] f = new int[n + 1];
    4.         for (int i = 1; i <= n; i++) {
    5.             int minn = Integer.MAX_VALUE;
    6.             for (int j = 1; j * j <= i; j++) {
    7.                 minn = Math.min(minn, f[i - j * j]);
    8.             }
    9.             f[i] = minn + 1;
    10.         }
    11.         return f[n];
    12.     }
    13. }
    14.

    代码随想录 (programmercarl.com)

  • 相关阅读:
    撸完这个springboot项目，我对boot轻车熟路！【源码+视频都开源】【强烈建议收藏】
    Android Studio入门——页面跳转
    Llama2-Chinese项目：3.1-全量参数微调
    代理模式详解
    qlib因子分析之alphalens源码解读
    解析java中的String类中的方法(一)
    解决Edge游览器龟速下载问题
    JVM—类加载子系统
    冰箱“扩容”的战事，在今夏格外猛烈
    【安全】linux audit审计使用入门
  • 原文地址：https://blog.csdn.net/m0_63297917/article/details/133177339