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

5321 ワード
C どうてきけいかくほう boj アルゴリズム#アルゴリズム# テキストリンク
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)
    Drools学習ノート2
    [開発ログ]アプリケーション開発2週目:ホームページの作成