• 代码随想录刷题|动态规划理论基础 LeetCode 509. 斐波那契数 70. 爬楼梯 746. 使用最小花费爬楼梯

    动态规划理论基础

            递归算法是一种穷举的展示，任何数学递推公式都可以直接转换成递归算法，递归算法是当前层需要上一层的准备。递归算法冗余计算的增长是爆炸性的。如果编译器的递归模拟算法要是能够保留一个预先算出的值的表，而对已经解过的子问题不用再进行递归调用，那么这种指数式的爆炸性的增长就可以避免

            动态规划就是这样的算法

            如果某一个问题可以解决很多重叠问题，那么使用动态规划是最有效的解决办法

            动态规划中的每一个状态是由上一个状态推导出来的，这和贪心算法是不同的，贪心算法是没有状态推导的过程，贪心算法都是在当前局部选取最优解。所以贪心算法解决不了动态规划的问题

            动态规划五部曲：
                    1、确定dp数组（dp table）及下标的含义
                    2、确定递推公式
                    3、初始化dp数组
                    4、确定遍历顺序
                    5、举例推导dp数组

    509. 斐波那契数

    题目链接：力扣

    思路

    下面是对递归的优化：

            用表优化递归

            从这道题目可以看出，递归算法是需要不断向下进行计算，进行压栈，比如要算F(5)，那就要先算出F(4)和F(3)，就要先算出F(3)、F(2)、F(2)、F(1)……，这里可以看到是有重复的运算的

            那我们可以先创建一个数组（表），能够保留一个预先算出的值，这样就可以不用，这样就避免了重复的运算。已经算过的F(n)就不用再进行重复的计算

            根据动态规划五部曲：
                    1、确定dp数组（dp table）及下标的含义
                            第i个下标存储的是F(i)斐波那契的值
                    2、确定递推公式
                            递推公式是：dp[i] = dp[i - 1]+dp[i - 2]
                    3、初始化dp数组
                            dp[0] = 0;
                            dp[1] = 1;
                    4、确定遍历顺序
                            从递推公式可以得出，后面的数字依赖前面的数字，所以是从前向后遍历
                    5、举例推导dp数组
                            0 1 1 2 3 5 8 13 21 34 55

    下面是对表的优化：

            得出动态对话的代码之后会发现，代码的内存消耗比较大，我们发现处理，中间过程中的数字不都用，但是还是占用了内存，这样的内存占用时浪费的。比如F(10)。dp数组为：0 1 1 2 3 5 8 13 21 34 55。但是只会返回55，前面的都不用

            其实只需要维护两个数值就可以了，不需要记录整个数列。在整个遍历的过程中
            dp[0] = dp[i - 1]
            dp[1] = dp[i - 2]
            最后循环结束的时候dp[1]就是我们要的值

    斐波那契数

    递归思路

     

    1. class Solution {
    2.     public int fib(int n) {
    3.  
    4.         // 终止条件
    5.         if (n <= 1) {
    6.             return n;
    7.         }
    8.     
    9.         return fib(n - 1) + fib(n - 2);
    10.     }
    11. }

    动态规划

     

    1. class Solution {
    2.     public int fib(int n) {
    3.  
    4.         if (n == 0) {
    5.             return 0;
    6.         }
    7.         if (n == 1) {
    8.             return 1;
    9.         }
    10.  
    11.         // 创建数组
    12.         int[] dp = new int[n + 1];
    13.  
    14.         dp[0] = 0;
    15.         dp[1] = 1;
    16.  
    17.         for (int i = 2; i <= n; i++) {
    18.             dp[i] = dp[i - 1] + dp[i - 2];
    19.         }
    20.  
    21.         return dp[n];
    22.  
    23.  
    24.     }
    25. }

    动态规划(优化数组)

    1. class Solution {
    2.     public int fib(int n) {
    3.  
    4.         if (n <= 1) {
    5.             return n;
    6.         }
    7.  
    8.         // 创建数组
    9.         int[] dp = new int[2];
    10.  
    11.         // 初始化数组
    12.         dp[0] = 0;
    13.         dp[1] = 1;
    14.  
    15.         // 遍历实现数组
    16.         for (int i = 2; i <= n; i++) {
    17.             int sum = dp[0] + dp[1];
    18.             dp[0] = dp[1];
    19.             dp[1] = sum;
    20.         }
    21.  
    22.         return dp[1];
    23.     }
    24. }

    70. 爬楼梯

    题目链接：力扣

    思路

            本题也是动态规划的简单题，但是从这一道题目就可以发现动态规划的难点就在于去发现递推公司，这道题目本质上是一道斐波那契数列，但是发现并不容易，推导起来也不是很好想

            题目中要求的每次可以爬1或者2个台阶，也就是说，最终到达n阶台阶有两种方式，一个是爬1阶台阶到达（对应的是从n-1阶台阶开始），那么另一个就是爬2阶台阶到达（对应的是从n-2阶台阶开始爬），而爬n-1阶和n-2阶台阶的方法有dp[n - 1]，dp[n - 2]个。所以最终爬n阶台阶的方法种类就是dp[n -1 ]+dp[n -2]。其实也就是从n-1和n-2阶爬上去，探究的是几种走法，而不是几步

            台阶   几种方法
               1          1
               2          2
               3          3
               4          5
               5          8

            从二阶到四阶的那二阶一步和从三阶到四阶的一阶一步本身没有产生新方法，所以是从二阶达到四阶和从三阶达到四阶的两种方式相加

            所以推导的过程是：
                    在到达第n层的上一步，我们只有两个选择，走一步，或者走两步。
                    如果是走一步，我们需要先通过 f(n-1)种方式到达 n-1 层
                    如果是走两步， 我们需要通过 f(n-2)种方式到达第 n - 2 层
                    所以综上有 f(n) = f(n-2) + f(n-1)

            至于要如何初始化dp[0] = 1还是dp[1] = 1 .我倒觉得这个不是大问题，只不过是在对代码的意义上的解释不同，dp[1] = 1更能体现出动态思路的意义，dp[0] = 1也没啥问题

    爬楼梯

    动态规划(优化数组)

    1. class Solution {
    2.     public int climbStairs(int n) {
    3.  
    4.         if (n <= 2) {
    5.             return n;
    6.         }
    7.  
    8.         // 创建dp数组
    9.         int[] dp = new int[3];
    10.  
    11.         // 初始化数组
    12.         dp[1] = 1;
    13.         dp[2] = 2;
    14.  
    15.         // 遍历更新数组
    16.         for (int i = 3; i <= n; i++) {
    17.             int sum = dp[1] + dp[2];
    18.             dp[1] = dp[2];
    19.             dp[2] = sum;
    20.         }
    21.  
    22.         return dp[2];
    23.     }
    24. }

    动态规划(变量替代数组)

    1. class Solution {
    2.     public int climbStairs(int n) {
    3.  
    4.         if (n <= 2) {
    5.             return n;
    6.         }
    7.  
    8.         int dp1 = 1;
    9.         int dp2 = 2;
    10.  
    11.         for (int i = 3; i <= n; i++) {
    12.             int temp = dp1 + dp2;
    13.             dp1 = dp2;
    14.             dp2 = temp;
    15.         }
    16.  
    17.         return dp2;
    18.     }
    19. }

    746. 使用最小花费爬楼梯

    题目链接：力扣

    思路

            确定dp数组、确定递推公式、初始化dp真的是不容易呀

    1、明确数组

            本体要求的是爬到某一台阶需要的最小花费，随意我们明确dp[]数组为 最小花费数组，其中下标i上的数代表到大第 i 层台阶需要花费的最小费用为 dp[i]

    2、递推公式

            数组明确之后，就是考虑怎么获取数组中的值，也就是怎么求取每个台阶的最小花费值。这里dp[i] 是有两种情况的
            第一种情况是从前一个台阶跳上来，那最小花费 = 到达前一个台阶的最小花费 + 前一个台阶对应的费用，也就是     dp[i] = dp[i - 1] + cost[i - 1]
            第二种情况是从前两个台阶跳上来，那最小花费 = 到达前两个台阶的最小花费 + 前两个台阶对应的费用，也就是 dp[i] = dp[i - 2] + cost[i - 2]
            那这两种情况中最小的，就是我们要求的当前台阶对应的最小的费用

    3、初始化dp数组

            首先要明确一点就是，当站在下标【0】和下标【1】的时候是不消耗费用的，只有向上跳才会消耗费用，所以这里的初始化是比较重要的，要不然后面的结果也就不同了

    使用最小花费爬楼梯

    动态规划(使用数组)

    1. class Solution {
    2.     public int minCostClimbingStairs(int[] cost) {
    3.  
    4.         // 定义数组
    5.         int[] dp = new int[cost.length + 1];
    6.  
    7.         // 初始化数组
    8.         dp[0] = 0;
    9.         dp[1] = 0;
    10.  
    11.         // 遍历填充dp数组
    12.         for (int i = 2; i < dp.length; i++) {
    13.             dp[i] = Math.min(dp[i-1] + cost[i-1],dp[i -2] + cost[i-2]);
    14.         }
    15.  
    16.         return dp[cost.length];
    17.     }
    18. }

    动态规划(使用变量)

    1. class Solution {
    2.     public int minCostClimbingStairs(int[] cost) {
    3.  
    4.         // 初始化
    5.         int dp0 = 0;
    6.         int dp1 = 0;
    7.  
    8.         // 遍历更新
    9.         for (int i = 2; i <= cost.length; i++) {
    10.  
    11.             int dpi = Math.min(dp1 + cost[i-1],dp0 + cost[i-2]);
    12.             dp0 = dp1;
    13.             dp1 = dpi;
    14.         }
    15.  
    16.         return dp1;
    17.     }
    18. }

  • 相关阅读:
    Python + Django4 搭建个人博客（十二）:实现删除文章功能页面
    STC 51单片机41——汇编 串口连续发送数据
    用Java实现扑克牌游戏——简易炸金花
    基于PHP的连锁酒店管理系统
    【前端缓存】localStorage是同步还是异步的？为什么？
    python的文件目录操作 1
    Linux实操篇-定时任务调度
    TResNet: ResNet改进，实现高精度的同时保持高 GPU 利用率
    [echarts] 折线图+柱状图，多 Y 轴
    大厂SQL题5-同时在线人数、不同类别的第一
  • 原文地址：https://blog.csdn.net/m0_62575233/article/details/127916352