12 极客大学-算法训练营-覃超-第十二课.pdf

动态规划（Dynamic programmer - DP）

参考链接

动态规划

12.动态规划 - 图1

斐波那契数列

状态转移方程： 12.动态规划 - 图2
1、暴力解法 12.动态规划 - 图3

  1. function fib(n){
  2.     if (n <=1) {
  3.     return n;
  4.   }
  5.   return fib(n-1) + f(n-2)
  6. }

2、带备忘录的递归解法 O(n)

  1. var fib = function (n) {
  2.   if(n<=1){
  3.       return n;
  4.   }
  5.   let memo = []
  6.   if(memo[n] === undefined){
  7.       memo[m] = fib(n-1) + fib(n-2)
  8.   }
  9.   return memo[n];
  10. };

3、DP数组的迭代解法 O(n) 自底向上

  1. var fib = function(n){
  2.   let db = []
  3.   db[0] = 0,db[1]=1;
  4.   for(let i=2;i<=n;i++){
  5.       dp[i] = dp[i-1] + dp[i-2]
  6.   }
  7.   return dp[n];
  8. }

4、”状态压缩“ 迭代法 O(n)

  1. var fib = function (n) {
  2.   if (n <=1) {
  3.     return n;
  4.   }
  5.   let prev = 0,
  6.     curr = 1;
  7.   for (let i = 2; i <= n; i++) {
  8.     let sum = prev + curr;
  9.     prev = curr;
  10.     curr = sum;
  11.   }
  12.   return curr;
  13. };

322. 零钱兑换

base case: amount = 0
状态：amount
选择: coins[]
明确DP函数定义

备忘录

  1. // 自顶向下 - 备忘录
  2. var coinChange = function (coins, amount) {
  3.   let memo = [];
  4.   return dp(coins, amount, memo);
  5. };
  6. var dp = function (coins, amount, memo) {
  7.   if (memo[amount]) {
  8.     return memo[amount];
  9.   }
  10.   if (amount == 0) {
  11.     return 0;
  12.   }
  13.   if (amount < 0) {
  14.     return -1;
  15.   }
  17.   let res = Infinity;
  18.   for (let coin of coins) {
  19.     subproblem = dp(coins, amount - coin, memo);
  20.     if (subproblem == -1) continue;
  21.     res = Math.min(res, 1 + subproblem);
  22.   }
  23.   memo[amount] = res;
  24.   return res != Infinity ? res : -1;
  25. };

实战题目