个人学习博客

# 动态规划

  • 解决问题：不同路径，最短路径
  • 3个概念：状态转移方程，最优子结构，边界
  • 数学思想：分阶段解决问题
  • 动态规划是全局最优，贪心算法是当前最优
  • 动态规划是dp，动态递推
  • 背包问题，打结问题，路径问题，最小路径和 322零钱兑换

# 斐波那契数列

0,1,1,2,3,5,8,13,21,34......
function fib(N){
  let cached = [0,1]
  for(let i=2;i<=N;i++){
    cached[i] = cached[i-1]+cached[i-2]
  }
  return cached[N]
}
var fib = function(N) {
  if(N==0||N==1){
    return N
  }
  let prev=0, cur=1
  for(let i=2;i<=N;i++){
    let sum = prev+cur
    prev = cur
    cur = sum
  }
  return cur
};

# 寻找最长公共子串

let text1 = "abcde", text2 = "ace"
let lcs = function(s1,s2){
  let n = s1.length
  let m = s2.length
  let dp = Array.from(new Array(n+1), ()=>new Array(m+1).fill(0))
  for(let i=1;i<=n;i++){
    for(let j=1;j<=m;j++){
      if(s1[i-1]===s2[j-1]){
        dp[i][j] = dp[i-1][j-1]+1
      }else{
        dp[i][j] = Math.max(dp[i][j-1],dp[i-1][j])
      }
    }
  }
  return dp[n][m]
}

# 背包问题

let value = [4,5,10,11,13]
let size = [3,4,7,8,9]
let cap = 16
let n = 5
function getMaxValue(n,size,cap,value){
  let dp = Array.from(new Array(n+1),()=>new Array(cap+1).fill(0))
  for(let i=1;i<=n;i++){
    for(let w=1;w<=cap;w++){
      if(size[i-1]<=w){
        dp[i][w] = Math.max(value[i-1]+dp[i-1][w-size[i-1]], dp[i-1][w])
      }else{
        dp[i][w] = dp[i-1][w]
      }
    }
  }
  console.log(dp[n][cap])
}
getMaxValue(n,size,cap,value) //23

# 找零问题（322）

  • core: dp[i] = Math.min(dp[i], dp[i - coin] + 1)
  • dp[i]两种实现方法 ➡ 1.包含coin 剩余的钱就是i-coin 此时兑换的硬币数为dp[i - coin] + 1 (1为枚举coin本身) ➡ 2.不包含coin 此时兑换的硬币数为dp[i]
var coinChange = function(coins, amount) {
 if(amount==0){
   return 0
 }
 const dp = Array(amount+1).fill(Number.MAX_VALUE)
 dp[0] = 0
 for(let i=0;i<dp.length;i++){
   for(let j=0;j<coins.length;j++){
     if(i-coins[j]>=0){
       dp[i] = Math.min(dp[i], dp[i-coins[j]+1])
     }
   }
 }
 return dp[dp.length-1]===Number.MAX_VALUE ? -1 :dp[dp.length-1]
};

# 不同路径2

export default (arr, m, n)=>{
  let dp = (m,n) => {
    if(m===2&&n===2){
      return (arr[1][1]===1||arr[0][1]+arr[1][0]===2) ? 0 : (arr[0][1]===1||arr[1][0]===1)?1:2; 
    }else if(m<2||n<2){
      if(m<2){
        return arr[m-1].includes(1)?0:1;
      }else{
        for(let i=0;i<m;i++){
          if(arr[i][0]===1){
            return 0
          }
        }
        return 1;
      }
    }else{
      return dp(m-1,n)+dp(m,n-1)
    }
  }
  return dp(m,n)
}

← Introduction →