动态规划-爬楼梯.js

  1. // 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
  3. // 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
  5. // 注意：给定 n 是一个正整数。
  7. // 示例 1：
  9. // 输入： 2
  10. // 输出： 2
  11. // 解释： 有两种方法可以爬到楼顶。
  12. // 1.  1 阶 + 1 阶
  13. // 2.  2 阶
  14. // 示例 2：
  16. // 输入： 3
  17. // 输出： 3
  18. // 解释： 有三种方法可以爬到楼顶。
  19. // 1.  1 阶 + 1 阶 + 1 阶
  20. // 2.  1 阶 + 2 阶
  21. // 3.  2 阶 + 1 阶
  23. /**
  24.  * @param {number} n
  25.  * @return {number}
  26.  */
  27. let cache = { 1: 1, 2: 2, 3: 3 };
  28. var climbStairs = function (n) {
  29.     if(cache[n]) {
  30.         return cache[n]
  31.     }
  32.     var res = climbStairs(n - 1) + climbStairs(n - 2)
  33.     cache[n] = res
  34.     return res
  35. };

动态规划-泰波那契序列.js

  1. // 泰波那契序列 Tn 定义如下：
  3. // T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2
  4. // Tn = T(n-3) + T(n-2) + T(n-1)
  5. // 给你整数 n，请返回第 n 个泰波那契数 Tn 的值。
  7. // 示例 1：
  9. // 输入：n = 4
  10. // 输出：4
  11. // 解释：
  12. // T_3 = 0 + 1 + 1 = 2
  13. // T_4 = 1 + 1 + 2 = 4
  14. // 示例 2：
  15. // 输入：n = 25
  16. // 输出：1389537
  18. // 纯递归解法会超时
  20. let cache = {0:0, 1:1, 2:1}
  22. var tribonacci = function (n) {
  23.   if (n == 0) {
  24.     return 0;
  25.   }
  27.   if(cache[n]) {
  28.     return cache[n]
  29.   } else {
  30.     let res = tribonacci(n - 1)  + tribonacci(n-2) + tribonacci(n - 3)
  31.     cache[n] = res
  32.     return res
  33.   }
  34. };
  36. tribonacci(n)