高盛电面

面试官迟到十分钟,随便聊了聊就进入正题。

一共就只有一道题加followup; max path sum和[刷题]网站的unique path sum基本一样,dp解决。Follow up是如何打印最优的路径的坐标。

区别就在于也是要自己跑test case.,并且解释test case的理解理念。

请问follow up如何回答?用dfs么

请问楼主投的什么地区的职位?

我觉得不用,就另开一个二维数组记录坐标就可以。重点就在于记录max path是从哪个方向,左边还是下边过来的,可以记录左边过来的最大值为1,下边过来的最大值为2. 然后就可以记录下最优的路径。如果觉得我没说清,可以Google下九章的minimum path sum…里边有一个解法就是专门讲如何打印路径的,很受用