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前进。

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

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

在讲堂看“沦陷”

讲南京大屠杀，比较注重内心的戏。涉及了战争中各种人物的挣扎，有中国牧师，可怜的妇女，战败的军人，变节者，疯狂的日本人，国际组织工作者。

很长时间舞台上都是有张力的，有几个瞬间真的感动了我，相信多数观众也是。在谢幕的时候掌声的热烈程度明显受到了是否正面角色的影响。最大的瑕疵是演员都戴了兄麦，音效很差。第二天在英杰交流中心开座谈会，创作人员都很谦虚诚恳，表示非常看重北大的同学们的意见。

BBS上有剧社的人用很刻薄很没文化的语言批评这个戏，并有人称这是他看过最烂的戏。我不知道如果这个戏烂，那么他们做的“魔鬼与上帝”又该叫什么，而他们作为亲自制造垃圾的人，凭什么用恶毒的词汇向专业演员叫嚣，至少人家对舞台的态度是严肃的。那一刻，我为北大剧社感到悲哀，它确实没落了。

里面有一句台词很喜欢：“我们必须用自己的血肉铸成新的长城……只有这样，我们才有资格告诉我们的后代，在中华民族最危险的时刻，我们是不愿意做奴隶的人们”。

面纱

繁乱的社交，寂寞与背叛的纠缠已使她学会了如何在绝望中拯救自己，而命运却匆忙地为这一课
留下生离死别作为习题。最终的她的笑容，是一个女人所能给于的最完美解答，那一刻的气度，
高贵如女皇。而这样的残忍而迫不及待的情节铺排却用悠扬从容的音乐做衬，将压抑和诗情画意
侵染一起，有了特别的意蕴。

我从中看到无奈的部分一如生活本身，而里面我不愿或不敢直面的残忍，大概也如生活本身。

2007-03 自绝望中仰望

贯穿整个3月投入很多心血排“一个绝望的人”，是剧星的复赛，再获当晚最佳男演员，但未能晋级决赛。这个戏以我的标准来看有很多地方需要锤炼，但是和当晚其它的戏比仍然好很多，我们赢得了观众的认可，但没有得到评委老师的眷顾。排的过程很多辛苦波折，最后和大家的关系都很好，真的有“风雨同舟，生死与共”的感想。

决定此后努力做一个低调的人，轻轻地交谈，不急躁不动声色。很有耐心地对每一个人，仔细听轻声说。坚持宽厚的态度，不刻薄不吝啬。从容养气，宠辱不惊。唯其如此才能得到别人发自内心的尊敬。没有人会信任一个一直激情四射的人，也不会真正喜欢他或认可他。这是这个世界的规律，深入到人性里，远非中国文化的意志。性格里有很多刚硬的元素，喜欢在否定中坚持，动力便是外界的否定，很多时候这种心理在客观上让我显得不屈不挠，但在本质上它很接近强迫。

这个春天有些凉，但终是不可挽回地温暖起来。

一个绝望的人

说说我们排的一个绝望的人。排的时候我确实多次绝望，尤其演出前听说handy是嘉宾之一，再看陶婧一脸沮丧，弄得我差点崩溃。最后0.2分之差没有晋级决赛，不过我们三个是全场最佳男演员。得分高过我们的一个是先锋剧“车站”，一个是英文剧“美杜莎”，大家一直觉得“车站”和我们应该晋级，但是“北大剧星大赛”有一个传统，就是偏爱英文剧到匪夷所思的地步，上届的冠军是一个英文戏，烂的一塌糊涂，散场后一位评委老师说，“真厉害，从头到尾都是英语，一句中文都没有！”。我们的得到了在场观众的认可，但无法理解评委的心思。排练的时间很短，大家都投入了很多心血，过程非常精彩。附件里是评委的评分，视频据说这几天就会发给我们，一定想办法传给你看，用qq可以吗？

起初是这样的，快开学时初赛我们剧组的领队兼导演说这学期很忙不能导了，让我做领队组织一个戏。时间紧迫，我四处找导演找剧本，看了很多本子都不合适，后来突然想到你的那次演出。然后就去问陶婧愿不愿意导。她同意后开始四处找演员试戏，都是我找的但很多我根本没见过，舞台素质和导演的想象有相当差距，到演出前两周才把演员定下来，好在都是相对优秀的。

排的时候也有很多波折，开始演多尔比亚克的演员，也就是去年的导演，由于刚交了女朋友整日谈恋爱不背台词，我想了个办法让她mm鼓励他演，这才让他进入了正常状态。之后一天，演阿尔诺的研究生师兄不满导演的工作方式，不顾我们大家的一致反对，和导演就这个戏该如何导和导演及大家论战了一番，当天陶婧感冒。这是已过了一周，第二天本该彩排，陶婧说感冒得去不了，当时我非常愤怒，彩排时暗示另两位如果继续这样就让他们自己去演吧，本来这个剧组是政管代表队，只有他们是政管的。我走后多尔比亚克暗中和阿尔诺交流了一番，我向陶婧表达了我的歉意和感激，她决定坚持。之后的一个星期合作的越来越融洽，我渐渐可以把精力集中于表演，最后的两天大家渐渐有了信心。

这个戏真是很难演，加上这么短的时间，很多时候我在表演的时候严重缺乏自信。后来我仔细地看了很多遍你们的录像，有一天排练，我和多尔比亚克的对手戏中几乎完全模仿了你的动作，那是我最自信的一次，虽然当时的表演并未得到我想象中的认可。后来，导演多次让我不要模仿你的一些动作，说很难看，比如阿尔诺说”裁缝们给他做了细腰蜂似的外衣“时你撑自己的腰等等。但在上台的时候我多数都保留了，因为那时我唯一能快速找到自信的方式。你之于我一直是舞台的统治者，模仿你的时候我会觉得我和你站在一起，与舞台之神同在，还有什么值得畏惧？呵呵，确实是这样想的。

评委的评价我们的表演具备专业演员的素质，缺点有两个：一是应该对剧本中冗长的部分进行删减，二是多尔比亚克一出场就让人看出是骗子，这个包袱应该等伊维莱特上的时候再抖。我们一直把它理解成喜剧，而开始多尔比亚克和阿尔诺的戏长达15分钟，害怕那样演会演成正剧，观众习惯于那种节奏后，没法把情绪扭转过来。”尽早进入喜剧的气氛“是我们从最开始就坚持的一个想法。演出后不论是现场还是bbs上大家都对我们未能晋级表示意外，虽然只差在毫厘之间。这也引发了我思考，做戏究竟该如何去处理外界的评判和自己的追求。

陶婧为这个戏投入了很多时间和精力，我真的感动得不行。她时常谈你，现在和过去的好玩的事情。因她将爱你的部分热情折射于这个戏，我们便看到了这样投入得忘我能干到无敌的女子，我想这样的爱，如果硬要拿来和时空匹敌，至少要换五十年的光阴加上一个大海的宽度。她很多次提及接着个戏最主要是因为你，我想这是她表达对你的思念的一种方式，这样的恋人，值得用一生一世珍惜爱护。

对于你的表演，我一直羡慕敬佩得五体投地，但是仔细想想，各种的因缘错过，我只看过你演的一个戏，导的一个戏。如果说这次演”一个绝望的人“对我有什么意义，最大的意义莫过于对你表示想念和敬意。