Ai的维数为Pi-1 · Pi

可以递归地定义m[i,j]为：

2.3.4计算最优值

对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题。不同子问题的个数最多只 有：O(n^2)

在递归计算时，许多子问题被重复计算多次->重叠子问题

• 用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算，在计算过程中，保存已解决的子问题答案
• 每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重 复计算，最终得到多项式时间的算法

2.3.5用动态规划求解最优解

3.算法实现

3.1备忘录法

/*
int n;//输入的数的个数
int[] num;//储存数
int[][] m;//动态规划数组，保存当前最优解
int[][] s;//用于构造最优解
*/

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n;
        int[] num;
        int[][] m;
        int[][] s;
        while(scanner.hasNext()) {
            n=scanner.nextInt();
            num=new int[n];
            m=new int[n][n];
            p=new int[n];
            s=new int[n][n];
            for(int i=0;i<n;++i) {
                num[i]=scanner.nextInt();
            }
            int ans=Solve(1,n-1,m,num,s);
            System.out.println(ans);
        }
    }
    private static int Solve(int i, int j,int[][] m,int[] num,int[][] s) {
        if(m[i][j]>0)return m[i][j];                      
        if(i==j)return 0;
        int u=Solve(i+1, j, m,num,s)+num[i-1]*num[i]*num[j];
        s[i][j]=i;
        for(int k=i+1;k<j;++k) {
            int t=Solve(i, k, m, num, s)+Solve(k+1, j, m, num, s)+num[i-1]*num[k]*num[j];
            if(t<u) {
                u=t;s[i][j]=k;
            }
            m[i][j]=u;
        }
        return u;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

3.2动态规划

import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n;
        int[] num;
        int[][] m;
        int[][] s;
        while(scanner.hasNext()) {
            n=scanner.nextInt();
            num=new int[n+1];
            m=new int[n+1][n+1];
            s=new int[n+1][n+1];
            for(int i=0;i<n;++i) {
                num[i]=scanner.nextInt();
            }
            n=n-1;
            for(int i=1;i<=n;++i) {m[i][i]=0;}
            for(int r=2;r<=n;r++) {
                for(int i=1;i<=n-r+1;i++) {
                    int j=i+r-1;
                    m[i][j]=m[i+1][j]+num[i-1]*num[i]*num[j];
                    s[i][j]=i;
                    for(int k=i+1;k<j;k++) {
                        int t=m[i][k]+m[k+1][j]+num[i-1]*num[k]*num[j];
                        if(t<m[i][j]) {
                            m[i][j]=t;
                            s[i][j]=k;
                        }
                    }
                }
            }
            traceback(s,1,n);
            //System.out.println(m[1][n]);
        }
    }
 
    private static void traceback(int[][] s, int i, int j) {
        if(i==j)return;
        traceback(s, i, s[i][j]);
        traceback(s, s[i][j]+1, j);
        System.out.println("A["+i+":"+s[i][j]+"] * A["+(s[i][j]+1)+":"+j+"]");
         
    }
 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48