Google筆試的敗筆

1 超級失敗的1：說8點開始，考試時間100分鐘 ，怎么算都是9：10交卷；9點一到匆匆交卷了，晚上躺床上才發現錯也；

2 超級失敗的2：把自個的生日又記錯了；

3 怕怕的發現：發現mm還是超級可怕滴，眼睜睜看著一個騙局，哎，也得謹慎些以防上當受騙啊；

題目如下：

T( 0 ) = 1 ; T(1)=1;T(2)=2;T(n)=T(n-1)+T(n-2)+T(n-3);
用最優方式求T(n) ;

int?T(int?n)?{
}

可以用最熟悉的語言寫

在考場的第一個做法

?1 public ? class ?T? {
?2  ? public ? int ?t( int ?n) {
?3  ?? if ?(n? == ? 0 )? {
?4 ??? return ? 1 ;
?5  ??} ? else ? if ?(n? == ? 1 )? {
?6 ??? return ? 1 ;
?7  ??} ? else ? if ?(n? == ? 2 )? {
?8 ??? return ? 2 ;
?9  ??} ? else ? {
10 ??? return ?t(n - 1 )? + ?t(n - 2 )? + ?t(n - 3 );
11 ??} ?
12 ?}
13 }
當時發現時間夠用，進行了公式推理，但未得出規律的真諦
每個都與T(3)可以直接發生關系，關系是2的冪次方，但最終沒有得出公式
遂改進如下：

?1 public ? class ?T? {
?2  ? public ? int ?t( int ?n) {
?3  ?? if ?(n? == ? 0 )? {
?4 ??? return ? 1 ;
?5  ??} ? else ? if ?(n? == ? 1 )? {
?6 ??? return ? 1 ;
?7  ??} ? else ? if ?(n? == ? 2 )? {
?8 ??? return ? 2 ;
?9  ??} ? else ? {
10 ??? return ? 2 ? * ?t(n - 1 )? - ?t(n - 3 );
11 ??} ?
12 ?}
13 }

晚上躺床上，怎么可能這樣直接呢？
突然想到最起碼的一點就是重復數的計算，應該進行保存；
如果正向逐個求然后保存，可行；
如果倒向如何保存，尚未想好
大家來仁者見仁一下哦（有更好的思路的請指點）
public class T {
?Map values = new HashMap();
?
?public int t(int n){
??int result = 0;
??if (n == 0) {
??? result = 1;
??} else if (n == 1) {
???result = 1;
??} else if (n == 2) {
???result = 2;
??} else {
???result =? 2 * t(n-1) - t(n-3);
??}
??return result;
?}
}