递归实现 fibonacc

  1. function fibonacc(n) {
  2.   if (n < 2) {
  3.     return n;
  4.   } else {
  5.     return fibonacc(n - 1) + fibonacc(n - 2);
  6.   }
  7. }

能用动态规划解决的问题

  • 问题的答案依赖于问题的规模，也就是问题的所有答案构成了一个数列。
  • 大规模问题的答案可以由小规模问题的答案递推得到。

注意能用不代表适合，有时候可以直接推出最终答案。在许多场景， 显式式子是不易得到的，大多数情况下甚至无法得到，动态规划的魅力就出来了。

时间复杂度一般是多项式

应用动态规划——将动态规划拆分成三个子目标

  1. 建立状态转移方程 fibonacc(n - 1) + fibonacc(n - 2) = fibonacc(n)
  2. 缓存并复用以往结果
  3. 按顺序从小往大算
    1. function dynFib(n) {
    2.      let val = new    Array(n).fill(0)
    3.  if (n == 1 || n == 2) {
    4.      return 1;
    5.  }
    6.  else {
    7.      val[1] = 1;
    8.      val[2] = 2;
    9.      for (let i = 3; i <= n; ++i) {
    10.          val[i] = val[i - 1] + val[i - 2];
    11.      }
    12.      return val[n - 1];
    13.  }
    14. }

    leetcode 300

    给定一个无序的整数数组，找到其中最长上升子序列的长度。
    1. var lengthOfLIS = function (nums) {
    2.  let n = nums.length
    3.  if (n === 0) return 0;
    4.  let dp = new Array(n).fill(0)
    5.  for(let i=0;i<n;i++){
    6.      for(let j=0;j<i;j++){
    7.          if(nums[j]<nums[i]){
    8.              dp[i] = Math.max(dp[i],dp[j]+1);
    9.          }
    10.      }
    11.  }
    12.  return Math.max(...dp)
    13. };
  • 划分为最小优化结构，从只含一位的数组开始
  • 大循环遍历整个数组，i
  • 小循环遍历 i 之前的数，如果有比 nums[i] 小的数那么就在它的子序列加 1。
  • 但是加一之后的序列并不是最长序列，还有和上一轮的最长序列比较。
  • 整个过程需要不停地找某个元素的最长子序列加一，这就用到了动态规划。
  • dp[i] = Math.max(dp[i],dp[j]+1); 状态转移

    leetcode 198

    你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：
输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

零一思想：选还是不选，对每个元素考虑两种情况，计算结果。

  1. var rob = function(nums) {
  2.     const dp = []
  3.     const n = nums.length
  4.     if(n===0){
  5.         return 0 
  6.     }
  7.     dp[0]=0
  8.     dp[1]=nums[0]
  9.     for(let i=2;i<=nums.length;i++){
  10.         dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1])
  11.     }
  12.     return dp[n]
  13. };

  • dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]) 如果选 i 那么只需要考虑 dp[i-2] 如果你选 i 考虑 dp[i-2] + nums[i-1]

    总结

  • 先定义 dp 元素的意义，例如 300 中 dp[i] 指以它为结尾的最长序列，198 指打劫这户人家

  • 第二步骤：找出数组元素之间的关系式，状态转移
  • 第三步骤：找出初始值。

    leetcode 62

    一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。问总共有多少条不同的路径？

    步骤一、定义数组元素的含义

    由于我们的目的是从左上角到右下角一共有多少种路径，那我们就定义 dp[i] [j]的含义为：当机器人从左上角走到(i, j) 这个位置时，一共有 dp[i] [j] 种路径。那么，dp[m-1] [n-1] 就是我们要的答案了。

    步骤二：找出关系数组元素间的关系式

    想象以下，机器人要怎么样才能到达 (i, j) 这个位置？由于机器人可以向下走或者向右走，所以有两种方式到达
    一种是从 (i-1, j) 这个位置走一步到达
    一种是从(i, j - 1) 这个位置走一步到达
    因为是计算所有可能的步骤，所以是把所有可能走的路径都加起来，所以关系式是 dp[i] [j] = dp[i-1] [j] + dp[i] [j-1]。

    步骤三、找出初始值

    dp[0] [0….n-1] = 1; // 相当于最上面一行，机器人只能一直往左走
    dp[0…m-1] [0] = 1; // 相当于最左面一列，机器人只能一直往下走
    1. var uniquePaths = function (m, n) {
    2.   const dp = new Array(m).fill(new Array(n).fill(0))
    3.   for (let i = 0; i < m; i++){
    4.       dp[i][0] = 1;
    5.   }
    6.   for (let j = 0; j < n; j++){
    7.       dp[0][j] = 1;
    8.   }
    9.   for (let i = 1; i < m; i++) {
    10.       for (let j = 1; j < n; j++) {
    11.           dp[i][j] = dp[i-1][j] + dp[i][j-1]
    12.       }
    13.   }
    14.   return dp[m-1][n-1]
    15. };