矩阵乘法最优序列问题

Java dp

发布日期: 2018-11-14

文章字数: 212

阅读时长: 1 分

阅读次数:

该问题是给定一系列矩阵求一个最少乘法次数。
这是一个动态规划问题，状态转移方程

long thisCost = m[left][i] + m[i+1][right]+c[left-1]*c[i]*c[right];

进行求解

    /**
     * 
     * @param c[0]为1矩阵行数 c 所有矩阵列数
     * @param m[i][k] 从i乘到j需要运行乘法最少次数
     * @param lastChang 最后一次改变的i值
     */
public static void optMatrix(int c[], long m[][],int lastChang[][]) &#123;
        int n = c.length - 1;
        for(int left = 1; left <= n; left++)
            m[left][left] = 0;
        for(int k = 1; k<n;k++) &#123;
            for(int left = 1; left<=n-k;left++) &#123;
                int right = left + k;
                m[left][right] = Integer.MAX_VALUE;
                for(int i = left; i < right; i++) &#123;
                    long thisCost = m[left][i] + m[i+1][right]+c[left-1]*c[i]*c[right];
                    if(thisCost < m[left][right]) &#123;
                        m[left][right] = thisCost;
                        lastChang[left][right] = i;
                    &#125;
                &#125;
            &#125;
        &#125;

    &#125;