关于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]
};