桌子店面

lc19890306

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

本帖最后由 lc19890306 于 2019-8-23 18:48 编辑

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

lc19890306

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

xgj-iwnl

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

lc19890306

xgj-iwnl 发表于 2019-8-23 21:13
证明的话。。可以反推，最后一次merge就是总和，无论之前是如何merge的。然后一路这么递归下去，就是最小 ...

差不多吧不过面试这种事我是第一时间不会往贪心上边靠的面试官要求交流要求先写可行解不一定有时间能静下心来想清楚

xgj-iwnl

只知道用二维dp，dp[i][j]表示从i到j的最小合并值。n^2的空间复杂度。

lc19890306

xgj-iwnl 发表于 2019/08/24 09:13:43
只知道用二维dp，dp[j]表示从i到j的最小合并值。n^2的空间复杂度。

任选两数读题读题

xgj-iwnl

lc19890306 发表于 2019-8-24 09:36
任选两数读题读题

抱歉抱歉。弱弱问一问，任选2个的话，每次选最小的有没有问题？

lc19890306

xgj-iwnl 发表于 2019/08/24 09:46:26

抱歉抱歉。弱弱问一问，任选2个的话，每次选最小的有没有问题？

greedy不行比如 1 1 1 1

xgj-iwnl

lc19890306 发表于 2019-8-24 09:47
greedy不行比如 1 1 1 1

1 1 1 1 -> 2 1 1 (+2) -> 2 2 (+2) -> 4(+4)
有比这个更小的吗？

winechen9

随手问问楼主是投了后多久有面试的呀~

lc19890306

xgj-iwnl 发表于 2019/08/24 09:58:11

1 1 1 1 -> 2 1 1 (+2) -> 2 2 (+2) -> 4(+4)
有比这个更小的吗？

好像可以一个堆就行了但是得证明一下对不对

lc19890306

winechen9 发表于 2019/08/24 10:03:36
随手问问楼主是投了后多久有面试的呀~

忘了很久以前投的