前言
前端学算法还是有必要性的，不说当初大厂面试都考算法，就是做权限模块的时候，如果不懂点算法，写树结构的自定义遍历都写不进去。
明天把最近刷题的遇到的动静布局和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]};