在汽车GPS屏幕上播放手机视频需要哪些设置?# PDA - 掌中宝
s*u
1 楼
还只是胡思乱想,也不太严谨。欢迎指正。(只讨论目前算法面试题一般涵盖的范围)
前言:
我知道大家都会说当满足最优子结构、subproblem overlap的时候可以用dp。但其实这
个条件个人感觉不太实用。
1.比如不overlap的时候也可以用dp,只是效率不提高,还增加了space cost而已。(
所以这个原则应该是“适合用dp”,而不是“可以用dp”
另外且不说最优子结构,overlap有时候也较难判断,比如boggle game这个,路径一定
是有重复的,但是
subproblem却未必,因为前驱的访问节点会影响后驱节点的"胜利条件"。
2.另外,就算是有overlap,从实用的角度来说,dp(bottom-up)未必方便实现。比如
用DFS来判定二叉树中是否有某个节点(cc150的4.7),bool cover( root, p )本身是
单纯的DFS访问,subproblem不存在overlap;但对整个问题而言,cover不停的调用,
对整个问题而言subproblem存在overlap。同样的还有4.1.因为这两个题目都在DFS中使
用了DFS,递归函数中调用了递归函数。
恕我愚笨,如果用dp,我不知道怎么解决。但用memoization(top-down)就可以很方
便解决,从上往下递归时顺便存进table。
当然,这里实际的原因是,memoization本身就属于广义的dp,所以“当满足最优子结
构、subproblem overlap的时候可以用dp”还是成立的。
那么问题就来了,如何区分,memoization和狭义dp(循环,bottom-up)呢。
=============================================================
我自己是这么总结的:
解决从起点到终点的问题,也就是通过解决subproblem到达胜利条件的问题,
1.如果起点和终点已知,那么可以用dp,
比如n的阶乘,Fibonacci的非递归解法,爬楼梯问题,其实也是dp。
然后记录一个int set的所有子集,或者string的所有permutation(起点、终点都只有
一个就是数组的头尾)
还有就是比如leetcode的unique path,虽然看上去是dfs,但实际起点、终点都是固定
的,都只有一个。
或者word break问题,虽然看起来很花哨,但是起点和终点还是只有一个。
这些都可以用dp。
如果需要记录路径,用prev[n]数组来记录。
2.如果起点或终点未知,或者说非常多( 比如超过O(1) ),那么就用递归(通常是
backtracking
),比如boggle game,比如二叉树判断一个节点是否在里面,比如组一个最高的box的
堆(cc150 9.10)。如果有overlap的情况,再引入memoization。
如果需要记录路径,用一个vector inplace操作即可
其实我相信这种情况还是可以用dp解的,不过问题瞬间复杂许多,感觉远远超出了面试
的需要。特别是不少情况用memoization,大体上可以妥协一下。
//当然,这里没有包含BFS这种方式。事实是,我们没有考虑贪心算法,比如dijkstra
算法(BFS时期特殊形式),比如longest increasing sub-sequence的贪心解法。至于
贪心算法和dp到底什么关系,我还在研究。。。
前言:
我知道大家都会说当满足最优子结构、subproblem overlap的时候可以用dp。但其实这
个条件个人感觉不太实用。
1.比如不overlap的时候也可以用dp,只是效率不提高,还增加了space cost而已。(
所以这个原则应该是“适合用dp”,而不是“可以用dp”
另外且不说最优子结构,overlap有时候也较难判断,比如boggle game这个,路径一定
是有重复的,但是
subproblem却未必,因为前驱的访问节点会影响后驱节点的"胜利条件"。
2.另外,就算是有overlap,从实用的角度来说,dp(bottom-up)未必方便实现。比如
用DFS来判定二叉树中是否有某个节点(cc150的4.7),bool cover( root, p )本身是
单纯的DFS访问,subproblem不存在overlap;但对整个问题而言,cover不停的调用,
对整个问题而言subproblem存在overlap。同样的还有4.1.因为这两个题目都在DFS中使
用了DFS,递归函数中调用了递归函数。
恕我愚笨,如果用dp,我不知道怎么解决。但用memoization(top-down)就可以很方
便解决,从上往下递归时顺便存进table。
当然,这里实际的原因是,memoization本身就属于广义的dp,所以“当满足最优子结
构、subproblem overlap的时候可以用dp”还是成立的。
那么问题就来了,如何区分,memoization和狭义dp(循环,bottom-up)呢。
=============================================================
我自己是这么总结的:
解决从起点到终点的问题,也就是通过解决subproblem到达胜利条件的问题,
1.如果起点和终点已知,那么可以用dp,
比如n的阶乘,Fibonacci的非递归解法,爬楼梯问题,其实也是dp。
然后记录一个int set的所有子集,或者string的所有permutation(起点、终点都只有
一个就是数组的头尾)
还有就是比如leetcode的unique path,虽然看上去是dfs,但实际起点、终点都是固定
的,都只有一个。
或者word break问题,虽然看起来很花哨,但是起点和终点还是只有一个。
这些都可以用dp。
如果需要记录路径,用prev[n]数组来记录。
2.如果起点或终点未知,或者说非常多( 比如超过O(1) ),那么就用递归(通常是
backtracking
),比如boggle game,比如二叉树判断一个节点是否在里面,比如组一个最高的box的
堆(cc150 9.10)。如果有overlap的情况,再引入memoization。
如果需要记录路径,用一个vector inplace操作即可
其实我相信这种情况还是可以用dp解的,不过问题瞬间复杂许多,感觉远远超出了面试
的需要。特别是不少情况用memoization,大体上可以妥协一下。
//当然,这里没有包含BFS这种方式。事实是,我们没有考虑贪心算法,比如dijkstra
算法(BFS时期特殊形式),比如longest increasing sub-sequence的贪心解法。至于
贪心算法和dp到底什么关系,我还在研究。。。