请教一道google面经题

在别人的面经上看到的题：“给一个int[]和一个int k，要求移除一些int[]数组中的元素来minimize sum ( abs ( arr_i - arr_i+1 ) ^ 2 )”
这个面经可能描述的不够清楚，就

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

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

46):
@magicsets 这位老哥使用的DP正解，设dp[i][j]的含义以及递推关系都非常的巧妙和精彩，66666

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

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

arr_i-arr_i？是不是表述有误啊

至少给个别人的链接 能看一下描述 你的描述明显有问题吧

从最简单的暴搜开始 用backtracking, 然后看看之中是不是可以存冗余的计算 变成memory版本的backtracking

yut210 发表于 2018-11-15 14:06
至少给个别人的链接 能看一下描述 你的描述明显有问题吧

第一行括号内部分就是我完全复制过来的了...是它本来就描述的有问题

Lcq3527 发表于 2018-11-15 14:02
arr_i-arr_i？是不是表述有误啊

后面那个是i+1啊

相当于一个N点图找权值和最小的长为N-K的路径

补充内容 (2018-11-16 02:06):
用DP可以找出所有以a[i]结尾的长为j (1<=j<=n-k) 的最大路径， 复杂度接近O(n^3)