[アルゴリズム][BOJ]11049行列乗算順序

BOJ_11049

💡 考えてみましょう。

[ダイナミックプランニングの開発プロセス]
1.再帰関係の確立(recursive property)
2.アップメソッド(bottom-up)を使用して解く
再帰関係
A[i][j]:M(i)からM(j)までの行列を乗じる最小乗算回数
A[i][j] = minimum(A[i][k] + A[k+1][j] + d(i-1)d(k)d(j)) (i <= k <= j-1)
A[i][i] = 0

💻 インプリメンテーション

A[i][j]の関数

を求めます

int minMult() {
	// valid only when i<=j(upper triangle)

	for (int diagonal = 1;diagonal < n;diagonal++) {
		for (int i = 1;i <= n - diagonal;i++) {
			int j = i + diagonal;
			int min = INF;

			for (int k = i;k < j;k++) {
				int n_mul = A[i][k] + A[k + 1][j] + (d[i-1]*d[k]*d[j]);

				if (min > n_mul) {
					min = n_mul;
				}
			}

			A[i][j] = min;
		}
	}

	return A[1][n];
}

まず、上図に示すように、マトリクス中のi<=jの部分のみが使用される.
-1番目のfor文:対角線を基準に行い、1番の対角線からn-1番の対角線に繰り返します.
-2番目のfor文:iは1からnの対角線であり、jはi+の対角線である.
そして,k毎に行列乗算に必要な乗算回数を求め,最切り上げを更新する.繰り返し文が終了すると、A[i][j]に保存されます.

初期コールゲート

int res = minMult();

💥 発展する

改善点

対角線方向に進んでいる点は一人ではわかりにくい.問題を分析するときは手書きで、進捗状況を把握するのに役立ちます.

📌 参考までに

マイコード(Github)