算法系列
动态规划是什么
动态规划(英语: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. 凑零钱问题
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))
注意:边界条件
- 先将res 设置为
Infinity
无限大 - 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))