From n to n-1

For most DP and searching problems, it's vital to reduce the original problem of size n to a new problem of the same the with size n-1. It's gennerally good if a f(n) problem can be solved by a constant number of f(n-1) problem, resulting a DP. If we can only reduce it to h(n) problems of f(n-1), often it's an exhausting searching problem where pruning or memorizing technique must be used.

Of course, “n” mentioned above is not confined to an integer. It may refer to a pair like (p,q), if f(p,q) can be solved by solving f(p,q-1), it's also a DP.

Let's illustrate the above idea with an example. f is a function mapping a sequence a1, a2, a3, ..., aN to a value. If we can find a g, s.t.

f(a1,a2,...,aN) = g(f(a1,a2,...,aN-1))

and g is easy to compute(which is often the case), we are in a happy situation. If, on the other hand, we have to solve each N-1 sized problem: f(a2,...,aN), f(a1,a3,...,aN), f(a1,a2,a4,...,aN), ..., f(a1,a2,...,aN-1) before we know the value of f(a1,a2,...,aN), it's a costly search problem.

Unfortunately, the ideal reduction is often difficult to find while the costly one is almost always at hand. More often than not, the problems we face can be solved far more efficiently than we are first willing to believe.

Why Google?

“我们必须全力以赴，咬紧牙关去做一件事情，否则我们必将一事无成”。

我想去Google工作，已经想了很久。Google对我来说也许是一个新的起点，但一枚Google的offer，更重要的意义是做一个光辉的重点以及前进的风标，一枚offer足矣。

Google的待遇并非最好，有很多关于那里工作环境的优美形容，不过哪个同级别的公司不是呢。Google唯一不能替代的是对于程序员来说，巅峰荣誉的象征。Google说“We hire the best people”，他们确实如此。因此，能进Google说明你是最优秀的，是对自己能力的有力证明。也许那里的生活并不适合我，但这不重要，我需要的是用它的offer证明自己。既然选择了做程序员，不论是不是当成终身职业，都应该做到最好，这是给自己当初选择的交代。

好了，这个想法给了我前行的动力。总地来说，我喜欢算法实践，但是这份喜爱远不足以是我努力钻研，Google的荣誉象征以及高薪把这份喜爱变成了任务。现在我必须全力投入这个任务，这改变了一直以来生活的节奏，一切将按照我喜欢的速度进行。这次Google的任务和高考，考研很像，目标明确，资料相对丰富，可以由简单重复线性积累成常人无法逾越的门槛，它使我的生活进入了可以高速前进的轨道。

2007-04 April is the cruellest month

四月是北京真正意义的春天。应该说北京的春天仅是四月天空的飘扬柳絮，稍纵即逝却温和美好。

前半月沉浸于“一个绝望的人”过后的空虚中。对编程的热情遭遇前所未有的危机，这部分是由于在做见过的最难的一道ACM:“限长最大平均值自列”，部分是对于未来目标的不明确，部分是由于性生活无着无落。在那道题陷了很久，最终看了一篇paper后搞定，真的很难。和一个奇怪的女孩去开了一次房，不知算不算一夜情。如同一次救赎，Google的出现在客观上拯救了我学业的危机。

后半月被Google占据。起初只是去参加笔试，目标不过是通过笔试而已，没想到笔试，一面很顺利地过关，好像天上掉下了香甜的馅饼。不过在最后一刻我被二面的很冷酷的工程师gg秒杀了，他问的问题我都无法回答，只能看着自己投机的梦想在他骄傲的颧骨下一步一步丧失体温。虽然当晚沮丧无比，终究这件事是积极的。它给了我考研之后最高的对于学习的热情。我会指定一些计划，向着Google前进。

认识了一个天蝎座的女孩，她记得见面那天是我妈妈的生日。如果在很早的时候认识她，可能现在的生活会很不同。不过这句话真没有意义。可能我在爱情上早已丧失了被拯救或者重生的机会，漫漫不归路，只能步步沦陷下沉。

月底已开始炎热，人群依旧嘈杂。