字节&leetcode70：爬楼梯问题 #90

Activity

1. sisterAn

   added

   LeetCode

   字节

   on Jul 29, 2020
2. sisterAn commented on Jul 29, 2020

   

   sisterAn

   on Jul 29, 2020

   Last edited by sisterAn

   OwnerAuthor

   More actions

   解法：动态规划

   动态规划（Dynamic Programming，DP）是一种将复杂问题分解成小问题求解的策略，但与分治算法不同的是，分治算法要求各子问题是相互独立的，而动态规划各子问题是相互关联的。

   分治，顾名思义，就是分而治之，将一个复杂的问题，分成两个或多个相似的子问题，在把子问题分成更小的子问题，直到更小的子问题可以简单求解，求解子问题，则原问题的解则为子问题解的合并。

   我们使用动态规划求解问题时，需要遵循以下几个重要步骤：

   • 定义子问题
   • 实现需要反复执行解决的子子问题部分
   • 识别并求解出边界条件

   第一步：定义子问题

   如果用 dp[n] 表示第 n 级台阶的方案数，并且由题目知：最后一步可能迈 2 个台阶，也可迈 1 个台阶，即第 n 级台阶的方案数等于第 n-1 级台阶的方案数加上第 n-2 级台阶的方案数

   第二步：实现需要反复执行解决的子子问题部分

   dp[n] = dp[n−1] + dp[n−2]

   第三步：识别并求解出边界条件

   // 第 0 级 1 种方案 
   dp[0]=1 
   // 第 1 级也是 1 种方案 
   dp[1]=1

   最后一步：把尾码翻译成代码，处理一些边界情况

   let climbStairs = function(n) {
       let dp = [1, 1]
       for(let i = 2; i <= n; i++) {
           dp[i] = dp[i - 1] + dp[i - 2]
       }
       return dp[n]
   }

   复杂度分析：

   • 时间复杂度：O(n)
   • 空间复杂度：O(n)

   优化空间复杂度：

   let climbStairs = function(n) {
       let res = 1, n1 = 1, n2 = 1
       for(let i = 2; i <= n; i++) {
           res = n1 + n2
           n1 = n2
           n2 = res
       }
       return res
   }

   空间复杂度：O(1)

   leetcode
3. sisterAn

   added

   腾讯

   on Sep 3, 2020
4. z253573760 commented on Feb 2, 2021

   

   z253573760

   on Feb 2, 2021

   Last edited by z253573760

   More actions

   function bar(nums) {
     if (nums === 0 || nums === 1) return 1;
     return bar(nums - 1) + bar(nums - 2);
   }
   function foo(nums) {
     const list = [1, 1];
     for (let i = 2; i <= nums; i += 1) {
       list[i] = list[i - 1] + list[i - 2];
     }
     return list[nums];
   }
   const res2 = foo(40);
   const res = bar(40);
   
   console.log(res === res2);
   
   

   👍React with 👍1Reacted by Flower
5. hugeorange commented on Dec 30, 2021

   

   hugeorange

   on Dec 30, 2021

   More actions

   这个问题好像就是斐波那契数列，动态规划是一种解法，也可以用尾递归

   function fib(n, ac1=1, ac2=1) {
     if (n <= 2) return ac2
     return fib(n-1, ac2, ac1+ac2)
   }