算法(二)——动态规划

479 阅读1分钟

算法系列

  1. 算法(一)——总述
  2. 算法(二)——动态规划

参考

动态规划是什么

维基百科

动态规划(英语:Dynamic programming,简称DP)是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的,通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

1.动态规划解决问题

动态规划常常适用于有重叠子问题和最优子结构性质的问题

刷题

1.斐波那契数列

leetcode 斐波那契数,通常用 F(n) 表示,形成的序列称为斐波那契数列。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:

F(0) = 0,   F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 给定 N,计算 F(N)。

a.暴力解法—— 自上而下

function fib(n){
    if(n ===1 || n ===2){
        return 1
    }
    return fib(n-1) + fib(n-2)
}

b.(二叉树剪枝)带备忘录的暴力解法

图中,蓝色部分都是重复出现的,f(4)与f(3),因为有触发出现,所以完全可以缓存了,也就传说中的剪枝

function fib(n, cache) {
  if (n === 1 || n === 2) {
    return 1
  }
  if (cache && cache[n]) {
      //console.log(n,cache)
    return cache[n]
  }
  cache[n] = fib(n - 1,cache) + fib(n - 2,cache)
  return cache[n]
}

function cacheFib(n) {
  var cache = {}
  fib(n, cache)
  //console.log('cache',cache) 
}
/************test *******************/
  console.log(cacheFib(5))

c.自底而上

function fib(n){
  if(n ===1 || n ===2){
      return 1
  }
  let dp =[0]
  dp[1] = dp[2] = 1
  for(let i=3; i<= n; i++){
    dp[i] = dp[i-1] + dp[i-2]
  }
  return dp[n]
}
/************ test *******************/
console.log(fib(20))

2. 凑零钱问题

leetcode

a.由上而下

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
const coinChange = function (coins, amount) {
    if(amount === 0){
        return 0
    }
    if(amount < 0){
        return -1
    }
    let res = Infinity
    for(const coin of coins){
        //subproblem 取值范围
        const subproblem = coinChange(coins, amount-coin) //subproblem 是 【-1,Infinity】
        if(subproblem === -1 ) continue  
        res = Math.min(res, subproblem+1)
    }
     //res 取值范围
    return res === Infinity ? -1 : res
};

/********************* test ************/
const coins = [1, 2, 5],
     amount = 21
console.log(coinChange(coins, amount))

注意:边界条件

  1. 先将res 设置为 Infinity无限大
  2. subproblem 是 【-1,Infinity】

核心是:定义一个变量,需要明确知道,每个变量的取值范围

b.剪枝——缓存

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
const coinChange = function (coins, amount) {
  const cache = {}
  const dp = function (amount) {
    if (cache[amount]) {
      return cache[amount]
    }
    if (amount === 0) {
      return 0
    }
    if (amount < 0) {
      return -1
    }
    let res = Infinity
    for (const coin of coins) {
      const n = amount - coin
      const subproblem = dp(n)
      if (subproblem === -1) continue
      res = Math.min(res, subproblem + 1)
      console.log(amount, n, res, cache)
    }
    const data = res === Infinity ? -1 : res
    cache[amount] = data
    return data
  }
  return dp(amount)
};

/****************test******************** */
const coins = [1, 2, 5],
  amount = 11
console.log(coinChange(coins, amount))

c. 由低向上

/**
 * @param {number[]} coins
 * @param {number} amount
 * @return {number}
 */
const coinChange = function (coins, amount) {
  const dp = Array.from({length:amount+1}).map( ()=> Infinity)
  dp[0] = 0
  for(let i=1; i<=amount; i++){
    for(const coin of coins){
      if(i<coin){
        continue
      }
      dp[i] = Math.min(dp[i],dp[i-coin]+1)
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount]
};

const coins = [1, 2, 5],
  amount = 21
console.log(coinChange(coins, amount))