【问题】面试题一个单调不减数组划分K组求划分K组后各组方差

2019/4/17镜像同步9 回复

给定一个数组和整数K eg.[5 9 13 17 21] k=3 划分K组之后比如[5,9] [13] [17,21] 求划分K组之后各组的方差加起来的最小值是多少 ------------------------ leetcode上有道是分为2组的左右遍历但是分为K组的有大佬有思路吗

订阅后，新回复会通过你的通知中心匿名送达。

9 条回复

A2017180197机器人#1 · 2019/4/17

直接dfs不行么

Gzern机器人#2 · 2019/4/17

可以但是面试官说复杂度太高了【在 A2017180197 的大作中提到: 】 : 直接dfs不行么

Rclover机器人#3 · 2019/4/18

感觉可以猜一个结论：划分的组应该都是原数组中连续的一段。然后就可以拿DP做了。dp[i][j]表示前i个数被划分为j组的最小方差之和。

Gzern机器人#4 · 2019/4/18

【在 Rclover 的大作中提到: 】 : 感觉可以猜一个结论：划分的组应该都是原数组中连续的一段。 : 然后就可以拿DP做了。dp[i][j]表示前i个数被划分为j组的最小方差之和。数组划分是连续的把整个数组切成K个部分 dp[i][j]如果i多加一个不切的话的状态方程没想好

Rclover机器人#5 · 2019/4/18

你别转移到i+1，转移到j+1 dp[k][j+1] = min(dp[k][j+1], dp[i][j]+(i+1,i+2,...,h的方差)) (h>i) 【在 Gzern 的大作中提到: 】 : : 数组划分是连续的把整个数组切成K个部分 : dp[i][j]如果i多加一个不切的话的状态方程没想好

Gzern机器人#6 · 2019/4/18

【在 Rclover 的大作中提到: 】 : 你别转移到i+1，转移到j+1 : dp[k][j+1] = min(dp[k][j+1], dp[i][j]+(i+1,i+2,...,h的方差)) (h>i) : 老哥这个k和h是什么意思 dp[i][j]+(i+1,i+2,...,h的方差) 是把(i+1,i+2,...,h的方差)当成切的最后一部分是吗

Rclover机器人#7 · 2019/4/19

啊，写错了，应该是dp[i][j]+(i+1,i+2,...,k的方差) 是你这么理解的【在 Gzern 的大作中提到: 】 : : 老哥这个k和h是什么意思 : dp[i][j]+(i+1,i+2,...,h的方差) 是把(i+1,i+2,...,h的方差)当成切的最后一部分是吗 : ...................

allvphx机器人#8 · 2019/6/8

惊现final大佬

bupt123机器人#9 · 2019/7/10

leetcode813

【问题】面试题 一个单调不减数组 划分K组 求划分K组后各组方差

【问题】面试题一个单调不减数组划分K组求划分K组后各组方差