Блог пользователя GODOF_Shinobi

How to solve this DP problem?
Автор GODOF_Shinobi, история, 6 лет назад, По-английски

This question was asked in a hiring round. As the round is over I am asking the question. Given N elements and a positive integer K divide the array into K segments/sub arrays such that maximum of sum of segments — minimum of sum of segments is minimized. Example given N=6 and K=3 a[]={7,2,3,1,2,3} .First segment is 7 ,Second is 2,3 and the Third is 1,2,3 .Max of {7,5,6} — Min of {7,5,6} = 2. While the N is pretty small. I would be thankful to any and all solutions possible.

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by GODOF_Shinobi (previous revision, new revision, compare).

→ Ответить
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The value of sum of segments is at most n^2 kinds at most. Brute-force attack the maximum and minimum values, f (idx, k, mi, ma): = Can you divide the interval of [idx, N-1] into k so that the divided minimum is mi and the maximum is ma?(bool) You can use dp.

→ Ответить
»
6 лет назад, # |
← Rev. 7   Проголосовать: нравится 0 Проголосовать: не нравится

nvm, wrong =(

→ Ответить
»
6 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

KN^2 dp[cur][from][used] //current position considering, start of where you re considering, how many segment youve made

the transition is either go to dp[cur+1][cur+1][used+1] or go to dp[cur+1][from][used]

I'm not sure how small N or K is, so I will offer this slow dp approach.

→ Ответить