这道题一种普遍的解法是动态规划。但是同样是动态规划,也有优劣之分。这篇博客贡献一份36ms(80%+)的答案,推荐这份答案不仅是因为速度,还是因为这种思路十分清晰,当然也可以参考讨论区中的7行的动态规划答案,也是十分优秀的。
每日归档: 2017年4月17日
LeetCode_373: Find K Pairs with Smallest Sums
寻找K个最大组合,博主最开始使用BFS来做的,算法复杂度$latex O(mn)$,计算和$latex mn$,广度优先搜索$latex V+E = mn+(m-1)(n-1)$,速度13ms。此外,博主对DP的掌握一直不够熟练,顺便贴了另一种使用DP的搜索方法,也是13ms,其实两种思路是差不多的。[mathjax]