問題定義

• 輸入：給定n個矩陣，矩陣間連乘

  a₁ ... a_n : a_i 與 a_{i + 1} 可乘

  令a₁：p₀ * p₁

    ...
  

  a_n：p_n-1 * p_n

  則：輸入用一維數(shù)組表示，P:{p₀p₁p₂...p_n}

• 輸出：求最少乘法次數(shù)的計算方法

  • 特征：無論在哪里斷開嫂拴，分開部分的矩陣作為一個整體不影響整個矩陣的連乘

  • 對于矩陣序列，不同的乘次序?qū)?dǎo)致不同的乘法次數(shù)

  • 例如：a₁ * a₂ * a₃的乘法次數(shù)

    (a₁ * a₂) * a₃ ：(p₀ * p₁ * p₂) + (p₀ * p₂ * p₃)

    a₁ * (a₂ * a₃)：(p₁ * p₂ * p₃) + (p₀ * p₁ * p₃)

  • 找出最優(yōu)計算次序以使得矩陣連乘所需要的計算次數(shù)最少

蠻力法

枚舉每一種劃分括號的情況晒旅，計算出他們的乘法次數(shù)，取最小的劃分情況

A1A2A3...An：添加括號汪诉，直到只有一個矩陣可以加括號废恋，然后計算他們的連乘次數(shù)

A1(A2(A3...An))的連乘次數(shù)：p2 * ... * pn + p1 * p3 * pn + p0 * p1 * pn

遞歸分治

優(yōu)化暴力枚舉（用k表示分割的位置）

每次調(diào)用遞歸式時：傳入分割后的矩陣列

遞歸出口：當(dāng)傳入的矩陣列中只有一個矩陣，返回0

回溯處理：計算兩邊分割乘法次數(shù)的和扒寄，計算兩邊合并的乘法次數(shù)再相加鱼鼓，取某個分割位置k時的最小值

• 優(yōu)點：存在子問題最優(yōu)解
• 缺點：存在重復(fù)計算部分
  • 為什么
    1. 遞歸使用幀無法保存太多的信息
    2. 子問題重疊，因為不同的部分劃分可能由相同的子問題組成该编，那么遞歸調(diào)用中出現(xiàn)重復(fù)計算的子問題是隨著遞歸深度變化的

動態(tài)規(guī)劃法

• 使用空間換時間迄本，將子問題記錄下來

  • 那么就將遞歸分治的缺點改為優(yōu)點，這下子课竣，解決方法就是利用了動態(tài)規(guī)劃的思想

• 令 m(i,j) ：為i嘉赎，j之間的矩陣列的最小乘法次數(shù)，在這之間使用k作為劃分的位置

  • 

  • 根據(jù)上述定義于樟，二維表m的對角線上都是0公条，m(1,n)是我們需要的最少乘法次數(shù)

• 令s(i,j)：為i，j之間矩陣列的最優(yōu)分割位置

• 時間復(fù)雜度：

  • for(1 to n)：枚舉序列長度

    • for(0 to r)：枚舉矩陣子列的起點

      • j = r

        for(k = i + 1 to j)：枚舉矩陣子序列分割點

        s表記錄最優(yōu)的分割位置迂曲、m表最少乘法次數(shù)
        

  • 線性時間讀s表靶橱，構(gòu)造最優(yōu)矩陣連乘的計算步驟

import java.util.Arrays;

public class MatrixChainTest {

    /**
     * @param p：矩陣維數(shù)序列，其長度減一為連乘矩陣的個數(shù)
     * @param memory：ai*...*aj的最小數(shù)乘次數(shù)
     * @param s：最佳括號斷開位置
     * 操作數(shù)組時路捧，從下標(biāo)開始
     */
    public static void matrixChain(int[] p, int[][] memory, int[][] s) {
        int n = p.length - 1;//矩陣個數(shù)
        //初始狀態(tài)對角線置為0
        for(int i = 0; i < memory.length; i++) {
            memory[i][i] = 0;
        }
        //矩陣長度從二(下標(biāo)0关霸，1)開始，計算不同子矩陣的數(shù)乘次數(shù)
        for(int r = 1; r < n; r++) {//r+1：矩陣列長度
            for(int i = 0; i < n - r; i++) {//從第一個矩陣開始杰扫，枚舉r+1長度的矩陣列（的起點）
                int j = i + r;//矩陣列：A_(i+1)*...*A_(j+1)
                //矩陣列長度：j - i + 1
                //斷開位置(矩陣列的第幾個(從1開始算)位置)與下標(biāo)關(guān)系：x_斷 = x_(下+1)
                //設(shè)最先斷開的位置是A_(i+1)
                memory[i][j] = memory[i][i] + memory[i+1][j] + p[i] * p[i + 1] * p[j + 1];
                s[i][j] = i + 1;
                //枚舉斷開位置队寇，在矩陣列：A_(i+1)*...*A_(j+1)的從 i+2 到 j+1
                for(int k = i + 1; k < j; k++) {//斷開位置從 k + 1開始
                    int temp = memory[i][k] + memory[k+1][j] + p[i] * p[k + 1] * p[j + 1];
                    if(temp < memory[i][j]) {
                        memory[i][j] = temp;
                        s[i][j] = k + 1;
                    }
                }
            }
        }
        System.out.println("矩陣連乘的最少乘法次數(shù)為" + memory[0][n - 1]);
    }

    /**
     * 利用矩陣序列最優(yōu)的分割位置s，構(gòu)造最優(yōu)計算次序
     * @param s：最優(yōu)分割位置
     * @return：矩陣序列p的最優(yōu)計算次序
     */
    private static String matrixChainMake(int[][] s) {
        int n = s.length;
        String[] temp = new String[n];
        //矩陣序列初始化
        for(int i = 0; i < n; i++) {
            temp[i] = "A" + i;
        }
        //加括號
        for(int i = 0; i < n - 2; i++) {
            int k = s[i][n - 1];//獲得分割的位置
            if(k - i > 1) {//括號包住兩個以上的矩陣列
                temp[i] = "(" + temp[i];
                temp[k - 1] += ")";
            }
            if(n - k > 1) {
                temp[k] = "(" + temp[k];
                temp[n - 1] += ")";
            }
        }
        //最后答案處理
        StringBuilder rs = new StringBuilder();
        for(int i = 0; i < temp.length; i++) {
            rs.append(temp[i]);
        }
        System.out.println("最優(yōu)計算次序為：" + rs.toString());
        return rs.toString();
    }

    /**
     *外部調(diào)用入口
     * @param p：矩陣列的維數(shù)
     * @return 返回矩陣連乘的最優(yōu)計算次序
     */
    public static String matrixChain(int[] p) {
        int[][] m = new int[p.length - 1][p.length - 1];
        int[][] s = new int[p.length - 1][p.length - 1];
        MatrixChainTest.matrixChain(p, m, s);
        System.out.println("m：");
        array2dShow(m);
        System.out.println("s：");
        array2dShow(s);
        return matrixChainMake(s);
    }

    public static void main(String[] args) {
        int[] p = {30, 35, 15, 5, 10, 20, 25};
        matrixChain(p);
    }

    private static void array2dShow(int[][] s) {
        for(int i = 0; i <s.length; i++) {
            System.out.println(Arrays.toString(s[i]));
        }
    }

}

相關(guān)鏈接：

• 09_動態(tài)規(guī)劃之矩陣連乘算法設(shè)計與分析嗶哩嗶哩_bilibili：推薦的講解視頻涉波，前面的引入和后面的思維發(fā)散都很有趣英上，引人深思
• 矩陣連乘：和視頻的講解思路一致
• 動態(tài)規(guī)劃之——矩陣連乘（全網(wǎng)最詳細(xì)博文，看這一篇就夠了Ｆ「病）：很詳細(xì)，很盡心的博文（沒代碼純思路惭聂，和視頻講解一樣

學(xué)習(xí)別人的思想窗声，總結(jié)自己的想法：

• 分析一個問題的解決方法，很容易想到暴力辜纲，然后再想著優(yōu)化笨觅，發(fā)現(xiàn)問題可以被分割成獨立的子問題拦耐，例如這題就朝分治遞歸去了；再分析遞歸分治的過程见剩，發(fā)現(xiàn)存在重復(fù)計算的子問題杀糯，那么出現(xiàn)了動態(tài)規(guī)劃問題的特性：最優(yōu)子結(jié)構(gòu)、子問題重疊
• 一步步的分析才能得到結(jié)果苍苞，不是觀測就來的

動態(tài)規(guī)劃基本步驟：
1.找出最優(yōu)解的性質(zhì)固翰，并刻劃其結(jié)構(gòu)特征。
2.遞歸地定義最優(yōu)值羹呵。
3.以自底向上的方式計算出最優(yōu)值骂际。
4.根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造最優(yōu)解冈欢。