个人随笔
目录
用动态规划的思想分析和解决leetcode的70题:爬楼梯问题
2021-08-26 22:24:17

题目

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?

分析

这题,如果做过斐波那契数列的话,一眼就看得出一模一样,但是我这篇文章的目的不是单纯的为了解题,还为了练习我们用动态规划解题的思想。

1、动态规划的本质是什么?

在我看来求解动态规划类型的问题的本质就是穷举

只不过,因为有重叠子问题,所以可以把子问题用一维数组或者二位数组缓存起来,求解过程中就不用去多做一遍了。

2、主要难题点?

找到状态转移方程

如果我们能够找到状态转移方程,那么很容易就可以根据递归暴力破解。也可以把每个状态对应的结果缓存起来,提高效率(动态规划)。

3、怎么找到状态转移方程?

我们知道,能够用动态规划解的题目,都有两个特点

1、最优子结构
2、重叠子问题

如果一个问题步满足上面两个条件,那就不能用动态规划来解了。

找状态转移方程,首先要找到【状态】是啥,状态就是原问题和子问题中会变化的变量,在这个爬楼梯的例子中,原问题和子问题中会变化的两就是n(阶梯数);
当我们找到状态后,我们需要找到导致状态变化的行为,也就是【选择】,在爬楼梯的例子中,导致状态变化的行为就是爬楼梯是爬1还是爬2;
然后我们可以找到我们的【dp函数】通常输入是跟状态有关的,然后输出是结果,这个例子中输入是阶梯数n,输出是爬楼梯的方案数;
既然是递归的方式可以解决的,那我们还需要找到基准值,也就是当状态变化到最小的时候,可以直接知道结果的dp函数结果,这里是当n=1时,dp(n)=1;当n=2时,dp(n)=2;

然后我们根据题意,就很容易列出【状态转移方程】,在这个问题里,用户通过什么选择达到了状态n,这里有两种选择,爬1还是爬2,所以总方案数就是dp(n-1)+dp(n-2)

  1. dp(n)=dp(n-1)+dp(n-2):dp(1)=1;dp(2)=2

这里直接这样列出来了,没有写成数学公式。

解题

1、粗暴递归

我们可以根据状态转移方程很粗暴的用递归的方法求解

  1. public int op(int n) {
  2. if(n==1) {
  3. return 1;
  4. }
  5. if(n==2) {
  6. return 2;
  7. }
  8. //1、当前阶梯是上一阶梯爬一步上来的
  9. int one = op(n-1);
  10. //2、当前阶梯是上一阶梯爬两步上来的
  11. int two = op(n-2);
  12. return one+two;
  13. }

当然这样子效率肯定机器低下哎,毕竟我们这个状态转移方程存在有很多重叠子问题,如果化成一个树来分析会发现假设计算dp(9),那么左边的树是dp(8),右边的树是dp(6),都含有重叠子问题比如dp(5),随着n的增大,时间复杂度指数级上升O(2^n),所以我们需要用动态规划的方法,把子问题的解保存在一张dp表中,可以是一维数组或者二维数组甚至是n维数组,这个要看你的状态转移方程来定,比如这里就用一维数组就可以了。

2、动态规划的方式解决

  1. public int climbStairs(int n) {
  2. //dp函数是一个以为数组,存放的是阶梯n对应的方法数目
  3. int[] dp = new int[n];
  4. if(n>=1) {
  5. dp[0]=1;
  6. }
  7. if(n>=2) {
  8. dp[1]=2;
  9. }
  10. for(int i=2;i<n;i++) {
  11. dp[i]=dp[i-1]+dp[i-2];
  12. }
  13. return dp[n-1];
  14. }

其实如果对于这个问题,计算的值只会跟前面两个值有关,所以这里用一个大小为2的数组或者两个变量缓存子问题的解即可。

  1. public int climbStairs2(int n) {
  2. //dp函数是一个以为数组,存放的是阶梯n对应的方法数目
  3. if(n==1) {
  4. return 1;
  5. }
  6. if(n==2) {
  7. return 2;
  8. }
  9. int one=1;
  10. int two=2;
  11. int now=0;
  12. for(int i=2;i<n;i++) {
  13. now=one+two;
  14. one=two;
  15. two=now;
  16. }
  17. return now;
  18. }

总结

动态规划问题的解法

1、判断问题是否具有【最优子结构】,也就是子问题和子问题之间不会互相影响
2、判断问题是否具有【重叠子问题】,毕竟动态规划的本质就是穷举,只不过把子问题的解缓存了起来而已
3、确定【状态】,也就是原问题和子问题中会变化的变量,比如零钱找零问题的状态就是金额,爬楼梯问题的状态就是楼梯数目
4、确定【选择】,也就是导致状态变化的量,比如选择爬1还是爬2
5、确定【状态函数】,一般参数会包含状态,结果为目标值
6、确定【基准值】,也就是状态为0或者1或者2的时候,函数的值
7、列出【状态转移方程】
8、编码解决【缓存子问题结果

其实网上看到一个伪代码的例子总结很棒

  1. # 初始化 base case
  2. dp[0][0][...] = base
  3. # 进行状态转移
  4. for 状态1 in 状态1的所有取值:
  5. for 状态2 in 状态2的所有取值:
  6. for ...
  7. dp[状态1][状态2][...] = 求最值(选择1,选择2...)

参考:https://leetcode-cn.com/problems/fibonacci-number/solution/dong-tai-gui-hua-tao-lu-xiang-jie-by-labuladong/

 128

啊!这个可能是世界上最丑的留言输入框功能~


当然,也是最丑的留言列表

有疑问发邮件到 : suibibk@qq.com 侵权立删
Copyright : 个人随笔   备案号 : 粤ICP备18099399号