谈一谈动态规划和dfs
前言
前端学算法还是有必要性的，不说现在大厂面试都考算法，就是做权限模块的时候，如果不懂点算法，写树结构的自定义遍历都写不出来。
今天把最近刷题的遇到的动态规划和dfs做一个总结，希望对大家学习算法能有所帮助。
DP和dfs关系
动态规划（dp）:
- 是从下往上的一个遍历。
- 需要一个递推公式比如f(n)=f(n-1)+f(n-2)这种。
- 不需要递归只需要普通的迭代，所以性能好。
- 是从上往下的一个递归。
- 也需要一个递推公式比如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;
jdfs
不剪枝会超时，用缓存去剪枝，剪枝了一般效率还是打不过Dp,除非有非常好的剪枝策略
var coinChange = function(coins, amount) {
coins.sort((a,b)=>b-a)
let cache = {}
const dfs = (restamount)=>{if(restamount===0) return 0
if(restamount适合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. 打家劫舍【谈一谈动态规划和dfs】这个题目用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]
};
推荐阅读
- 2019-02-13——今天谈梦想（）
- （七）谈条件
- 山香|山香 善思 智学访谈
- 从我的第一张健身卡谈传统健身房
- 我在一条路上走了5年
- FBI怎么和恐怖分子谈判
- 跟身体谈恋爱
- 二论鲲鹏（夜话庄子2）
- 深入浅出谈一下有关分布式消息技术（Kafka）
- 快意恩仇