google phone interview SETI

forteller 发表于 2017-7-4 07:25
lz的N=i*j  我的N = j。另外时间N^2就是两个for套起来。

补充内容 (2017-7-4 07:26):

确实已经用了滚动数组。
N=i+1=j+1不是N=i*j

可以进一步用window来优化 time。但应该还是O(N)

1,
1,1
1,2,1
1,3,3,1
1,4,6,4,1

1.用二项式是最快 O(N) O(1)
2.DP 进一步优化（每row只算必须的，红色部分） O(N^2) O(N)
3.DP 只存一维数组 O(N^2) O(N) 或者 trade off 用 recursion+memory O(N^2) 这个只算红色部分 但是space O(N^2)
4.DP 存在2维数组 O(N^2) O(N^2)
5.recursion 无memory O(2^N）O(N)

一开始的方法是#3 DP。interviewer应该是要recursion的trade off的方法。

补充内容 (2017-7-7 13:20):
#3 recursion+memory space 应该是O(N)
所以比DP要好 不是trade off

rgc588 发表于 2017-7-7 13:18
1.用二项式是最快 O(N) O(1)
2.DP 进一步优化（每row只算必须的，红色部分） O(N^2) O(N)
3.DP 只存一维 ...

你好楼主，这里有个问题。方法2和方法3本质是一样的，都是只计算红色必须部分，只不过一个用循环实现，一个用递归，为什么两个的space不一样？recursion+memory的space是O(n^2)吧

能解釋一下為什麼只算紅色部分嗎？
還有直接丟出二項式解法感覺會被發現做過這題，反而給的回饋不好？

就做了一道吗？

数学解啊

我觉得这道题就是说。
你看
1
11
121
1331
计算 triangle[i][j] 只需要知道 i-1 j 和 i -1 j -1这两个值。
估计他是想让你根据这个算吧。

感觉recursion应该的内存应该是O(N^2/4)