请问一道狗家高频题目

经常在地里看到这个题目比如这里面的第一轮。。



还有这里的第四轮。。

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

的数组 一定要按顺序相乘在求和么？

谢谢

fengya 发表于 2020-10-27 07:59
非常感谢～ 可是感觉这个就是permutation 没get到为什么是dp。。请指教

DP有bottom up就是通常的递推公式，分成子问题计算
有top down, 就是递归 + memoization

这里如果用DP可以用top down
数组的左边k位组成left数组1 2, 3， 右边k位组成right数组 6, 5, 4

dfs(vector<int>& left, int i, vector<int>& right, int j, vector<int>& mul, vector<vector<int>>& memo)

max(left[0] * mul[0] + dfs(left, 1, right, 0, mul, memo)
       right[0] * mult[0] + dfs(left, 0, right, 1, mul, memo))

前面那个是解释为什么引入multiplier后问题跟以前的不一样
程序还是要这样写才容易写，尤其k可能会比较大的数的情况

multiplier里第 k个，要去乘以第k次取出来的数
加了multipilier, 取数的顺序就有关系了。

1 2 3 4 5 6， k = 3
比如之前的算法是求 1 + 2  + 3
然后去掉3，尝试 1 + 2 + 6
然后去掉2，尝试 1 + 5 + 6
比较这三组就可以了。

现在，同样尝试取6，可能有不同的顺序：6-1-2, 1-2-6, 1-6-2.

算法还是跟之前的类似。就是要考虑下所有的顺序
先取 1 2 3, 分别乘以multiplier,  1 * k1 + 2 * k2 + 3 * k3
然后去掉3, 尝试 1 2 6， 这里可能的顺序是把6分别插入 1 2的空隙里，成为 6-1-2, 1-6-2, 1-2-6, 分别乘以multipiler
然后去掉2, 尝试 1 5 6， 这里可能的顺序是把1分别插入 6 5的空隙里，成为 1-6-5, 6-1-5, 6-5-1, 分别乘以multipiler

非常感谢～ 可是感觉这个就是permutation 没get到为什么是dp。。请指教

hsierra 发表于 2020-10-27 14:29
DP有bottom up就是通常的递推公式，分成子问题计算
有top down, 就是递归 + memoization

请问有bottom up 的公式吗?