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