关于javascript:谈一谈动态规划和dfs

前言

前端学算法还是有必要性的，不说当初大厂面试都考算法，就是做权限模块的时候，如果不懂点算法，写树结构的自定义遍历都写不进去。
明天把最近刷题的遇到的动静布局和 dfs 做一个总结，心愿对大家学习算法能有所帮忙。

DP 和 dfs 关系

动静布局（dp）:

• 是从下往上的一个遍历。
• 须要一个递推公式比方 f(n)=f(n-1)+f(n-2)这种。
• 不须要递归只须要一般的迭代，所以性能好。

深度优先搜寻（dfs）:

• 是从上往下的一个递归。
• 也须要一个递推公式比方 f(n)=f(n-1)+f(n-2)这种。
• 从上往下递归遇到终止条件后又会一直的从下往上取值（递归实质），过程相似 dp
• 因为遍历所有可能性，所以性能特地差，个别会剪枝
• 个别剪枝手法就是按条件提前终止或者记忆化

分割

• 记忆化后的 dfs 其实实质上和 dp 差不多
• 因为两者都要递推公式，所以实践上 dfs 能解的题 dp 都能解
• 不过有的题适宜 dfs，比方 求解可能性 的题目

一道经典题目双解

leetcode322. 兑换零钱

dp

var coinChange = function(coins, amount) {
/**
    遍历 i
    dp(n) = min(dp(n-conin[i]) + 1) 
    */
    coins.sort((a,b)=>b-a)
    const arr = new Array(amount+1).fill(0)
    for(let i =1;i<=amount;i++){ 
        let curAmount = i // 总额
        for(let j=0;j<coins.length;j++){let curConin = coins[j] // 以后兑换硬币
            if(curConin<=curAmount){let res = arr[curAmount-curConin]+1 // 这个数必然大于等于 0
                if(res===0) continue // 等于 0 则这种找零不可取
                arr[i] = arr[i]===0?res:Math.min(arr[i],res) // 等于 0 还没有初始化, 先初始化一下
            }
        }
        if(!arr[i]) arr[i]=-1
    }
    // console.log(arr)
    return arr[amount]
    
};

dfs

不剪枝会超时，用缓存去剪枝，剪枝了个别效率还是打不过 Dp, 除非有十分好的剪枝策略

var coinChange = function(coins, amount) {coins.sort((a,b)=>b-a)
        let cache = {}
        const dfs = (restamount)=>{if(restamount===0) return 0
            if(restamount<coins[coins.length-1])  return -1 // 残余比最小面额还小则 无奈胜利兑换
            if(cache[restamount])return cache[restamount]
            if(restamount<coins[coins.length-1]) return 
            for(var i=0;i<coins.length;i++){if(coins[i]<=restamount){let res = dfs(restamount-coins[i])+1
                    if(res===0) continue
                    cache[restamount] = cache[restamount]?Math.min(cache[restamount],res):res
                }
            }
            // 当走到这里的时候 cache[restamount]理论曾经确定了   自顶向下深度优先遍历理论默认有一个自底向上的过程，所以天生比 dp 慢
            if(!cache[restamount]) cache[restamount]=-1
            return cache[restamount]
        }
        return dfs(amount)
};

适宜 dsf 的题目

leetcode46. 全排列

求解可能性的题目，非常适合用 dfs.
如果用 dp, 代码会很难组织

var permute = function(nums) {
    //dfs  
    /**
        dp(n) = dp(n-1)数组中每个元素在 i 地位 (0<=i<=n) 增加 n
     */
    const dfs=(nums)=>{// [1,2]
        if(nums.length===1) return [nums.slice(0,1)]
        const arr = dfs(nums.slice(0,-1))
        const res = []
            arr.forEach(item=>{for(var i=0;i<=item.length;i++){let addedItem = item.slice()
                    addedItem.splice(i,0,nums[nums.length-1])
                    res.push(addedItem)

                }
            })
        return res
    }
    return dfs(nums)
};

适宜 dp 的题目

leetcode198. 打家劫舍

这个题目用 dp 解就很清新，当然递推公式蕴含贪婪思维。

var rob = function(nums) {//dp(n) = max(dp(n-2)+nums[n] , dp(n-1))    总共有 N 家，贪婪。从左往右轮到第 N 家的时候的收益

    const dp = new Array(nums.length).fill(0)
    dp[1] = nums[0]
    for(let i=2;i<=nums.length;i++){dp[i] = Math.max(dp[i-2]+nums[i-1] , dp[i-1]) // 轮到第 i 家的收益
    }

    return dp[nums.length]
};