# 动态规划
- 解决问题:不同路径,最短路径
- 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 →