アルゴリズムの動的プログラミング

Question

配列数（配列10^5）から構成され、各パーティションの最小要素の合計が最大となるように配列をKパーティション（k < = 500）に分割する必要があります

と言うと、配列はa1、a2、a3 ......... ここでf（x）= min（a1、a2..ax）+ min（a（x + 1）、a（x + 2）... AY）+ ......（Z + 1）···（N）

今f（x）が最大

パーティションであるべきです連続していなければなりません。
必要な複雑さ。 （N * K）

Iは単に一つによって最大要素一方を固定し、それはK個のパーティションに分割することができるかどうかを確認しようとしたか、はい、私はFを算出した場合ではない、（X）

Answer 1

dp[i] = f(x)レット今

dp[n]=sum(array elements); 
//ie when number of partitions is n we return sum of elements as each element is in different partition 

症例ベース、

dp[i-1] = dp[i] - min of partition collapsed in this step 

- パーティションの数をf OP によって定義されるような（X）であるが、今それを解決開始でき i とき

ここで、各ステップで折りたたむ必要があるパーティションを見つけるだけで済みます。これは、一度に2つの隣接するパーティションを取得し、どのパーティションの折りたたみが最も好ましくないかを示すタブ（O（n）で行うことができる）を残すことによってブルートフォースで行うことができます。

したがって、全体的な時間の複雑さはO（n * n-k）と空間の複雑さはO（n）です。さて、これはスキルに限界があり、改善を手助けできる人は歓迎です。