解答一下google intern 那两个算法题

递归就没有懂。{:4_84:}

递归就没有懂。{:4_84:}
小K 发表于 2011-2-6 00:36

要想理解递归，首先你得理解递归。
http://www.google.com/search?q=recursion
hahh

求解释，为什么第二题会是递归呢？

求解释，为什么第二题会是递归呢？
小K 发表于 2011-2-6 15:09

简单的说，就是n+1长度数组的结果可以在n长度的结果基础上来计算，所以是递归。不用递归也可以。这个严格来说不能叫数学归纳，数学归纳是用来做数学证明的，不是算法。形式上有些类似。

14# Jawley

数据结构和算法导论里几乎一半算法的来源都可以看作数学归纳法

14# Jawley

数据结构和算法导论里几乎一半算法的来源都可以看作数学归纳法
wwwyhx 发表于 2011-2-6 02:52

还是先定义一下数学归纳法，再讨论吧

14# Jawley

数据结构和算法导论里几乎一半算法的来源都可以看作数学归纳法
wwwyhx 发表于 2011-2-6 15:52

你这是因果倒置。数学归纳法来源于递归思想，你说的一半算法也来源于递归思想。递归是源头，数学归纳法只是一种利用到递归的证明手段而已。

简单的说，就是n+1长度数组的结果可以在n长度的结果基础上来计算，所以是递归。不用递归也可以。这个严格来说不能叫数学归纳，数学归纳是用来做数学证明的，不是算法。形式上有些类似。
Jawley 发表于 2011-2-6 15:31

gotcha,
q2到底解法是什么呢？

gotcha,
q2到底解法是什么呢？
小K 发表于 2011-2-7 06:46

动态规划（DP）肯定可以，好像还有快速的办法，以前上算法课有相同的一道例题，不过我已经记不得了……

19# Jawley

Q2:记录波峰波谷到一个数组： 比如1，-1，3，4，-2，3,0....
f(1)读到第一个上升区间为止，比如1,-1,3 : 记录最低点-1,最大差3-（-1） = 4
f(2)读到第二个，读入-2,3， 因为-2<-1，最低点更新为-2。 这样新增的可能最大差为3-(-2) = 5
又因为5>4所以最大差为5， 在1,-1,3,4,-2,3之前最佳买入点为-2最佳抛售点为3.
这就是f(n)和f(n-1)的递推关系。

DP完全没必要，一个for循环搞定。DP的存在意义是避免递归实现而产生的重复计算，比如斐波纳妾数列或最小编辑距离。