拼多多第四题编程题解
由于第一个小时在面试，最后总的算下来只有半个小时在笔试，最后一题后面想了一个平方级别的算法，评论区貌似只有立方级别的做法。
首先枚举i,j表示最后两个是那两个位置，暂且叫做dpij。
然后我们考虑极端情况，全部是0，那么ij可以转移到任何一个位置，复杂度=状态数*状态转移=n^3
肯定是不行的。
那么怎么办，我们贪心一下，ij只转移到里ak=ai+aj，ak是离ij最近的位置，可以把后面的ak都不用考虑
这一步贪心可以省去一个n的复杂度。
然后就很简单了,由于上面的贪心，dpij只可能转移到唯一一个dp[i'][j']
状态转移只要O（1），状态数要n^2
总共就只要n^2
,最后不得不说，和他的公司名声相比，他家的笔试题质量不知好到哪里去了。（至少让我觉得题目还是有思考价值）
#春招##笔试题目#
投递携程等公司10个岗位 >
查看21道真题和解析