動的計画法の区間DPの問題がよくわかりません。
解決したいこと
アルゴリズムとデータ構造について学習している者です。
某学習本に、動的計画法の区間DPの解説を読んでいるのですが、よく分からず困っています。
ご存知の方、よろしければ解説をお願いしたく存じます。
悩んでいる問題
N個の要素が一列に並んでいて、これをいくつかの区間に分割したいものとします。
各区間[l,r)にはスコア C(l,r)が付いているものとします。
KをN以下の正の整数として、K+1個の整数、t0, t1, ... tKを
0 = t0 < t1 < ...tK = N
を満たすように取った時、区間分割 [t0,t1), [t1, t2), ..., [tK-1, tK)のスコアを
C(t0,t1) + C(t1, t2) + ... + C(tK-1, tK)
によって定義します。
N要素の区間分割の仕方を全て考えた時の考えられるスコアの最小値を求めてください。
例
上記問題の回答ソース
#include <iostream>
#include <vector>
using namespace std;
template <class T> void chmin(T& a, T b) {
if (a > b) a = b;
}
const long long INF = 1LL << 60;
int main(void){
int N;
cin >> N;
vector<vector<long long>> c(N + 1, vector<long long>(N + 1));
for (int i = 0; i < N + 1; i++) {
for (int j = 0; j < N + 1; j++) {
cin >> c[i][j];
}
}
vector<long long> dp(N + 1, INF);
dp[0] = 0;
for (int i = 0; i <= N; i++) {
for (int j = 0; j < i; j++) {
chmin(dp[i], dp[j] + c[j][i]);
}
}
cout << dp[N] << endl;
}
教えて欲しいこと・お伺いしたいこと
質問①
問題の「スコア」とは、具体的に何の値のことを指しているのでしょうか。
例えばC(0,3)だとしたら、0~3の間にある値（0 ,1, 2）の合計値のことを言っているのでしょうか。
それとも、ソースの以下の箇所
for (int i = 0; i < N + 1; i++) {
for (int j = 0; j < N + 1; j++) {
cin >> c[i][j];
}
}
にて、各区間（(0,0) , (0,1) ....(N, N)）のスコアを自分で独自で適当に設定しろということでしょうか。
（となると、Nの値が大きいほど入力する数も増えてかつ、iとjが同じ数値のときのスコアをどうするかも考慮しないといけない気が...。そういうものなのでしょうか...。）
質問②
①が前者の場合、配列Cの値は以下のようになり、
vector<vector<long long>> c = {
{0, 0, 1, 3, 6, 10, 15, 21, 28, 36, 45},
{0, 0, 1, 3, 6, 10, 15, 21, 28, 36, 45},
{0, 1, 0, 2, 5, 9, 14, 20, 27, 35, 44},
{3, 3, 2, 0, 3, 7, 12, 18, 25, 33, 42},
{6, 6, 5, 3, 0, 4, 9, 15, 22, 30, 39},
{10, 10, 9, 7, 4, 0, 5, 11, 18, 26, 35},
{15, 15, 14, 12, 9, 5, 0, 6, 13, 21, 30},
{21, 21, 20, 18, 15, 11, 6, 0, 7, 15, 24},
{28, 28, 27, 25, 22, 18, 13, 7, 0, 8, 17},
{36, 36, 35, 33, 30, 26, 21, 15, 8, 0, 9},
{45, 45, 44, 42, 39, 35, 30, 24, 17, 9, 0}
};
結果、配列dpの値は以下のようになるかと思います。
dp[0] = 0
dp[1] = 0
dp[2] = 1
dp[3] = 3
dp[4] = 6
dp[5] = 10
dp[6] = 15
dp[7] = 21
dp[8] = 28
dp[9] = 36
dp[10] = 45
この時、問題ではN要素の区間分割の仕方を全て考えた時の考えられるスコアの最小値と言っていますが、どこで区切っても最小値は45で変わらない気がします。
これは何を求めたいのでしょうか...。
読解力がない自分の問題だとは思うのですが、宜しければご教示のほど宜しくお願いいたします。
