矩阵乘法（动态规划）

问题描述
　　有n个矩阵，大小分别为a0*a1, a1*a2, a2*a3, …, a[n-1]*a[n]，现要将它们依次相乘，只能使用结合率，求最少需要多少次运算。
　　两个大小分别为p*q和q*r的矩阵相乘时的运算次数计为p*q*r。
输入格式
　　输入的第一行包含一个整数n，表示矩阵的个数。
　　第二行包含n+1个数，表示给定的矩阵。
输出格式
　　输出一个整数，表示最少的运算次数。
样例输入
3
1 10 5 20
样例输出
150
数据规模和约定
　　1<=n<=1000, 1<=ai<=10000。

对于动态规划的题，不须多言，只要指出两个东西，1是状态，2是状态转移方程
我们定义状态d（i,j)为第i到j个矩阵运算次数最小的值，默认（i<=j)
状态转移方程：d（i,j)=min{d(i,t)+d(t+1,j)+i.l*t.r*j.r }(t大于等于i小于j）

代码：

import java.util.Scanner;

public class Main 
{   
    static long dp[][];
    static M m[];
    public static void main(String[] args) 
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        m=new M[n+1];
        dp=new long[n+1][n+1];
        int x=sc.nextInt();
        for(int i=1;i<=n;i++)
        {
            int y=sc.nextInt();
            m[i]=new M(x,y);
            x=y;
        }//矩阵的输入
        System.out.println(find(1,n));//dp（1，n）即为所求
    }
    static long find(int l,int r)
    {
        if(dp[l][r]!=0)return dp[l][r];//如果不等于0，说明之前计算过，直接返回
        if(l==r)return 0;//显然
        if(l+1==r)return dp[l][r]=m[l].l*m[l].r*m[r].r;
        dp[l][r]=Long.MAX_VALUE;
        for(int i=l;i<r;i++)
        {
            dp[l][r]=Math.min(dp[l][r], find(l,i)+find(i+1,r)+m[l].l*m[i].r*m[r].r);//得到dp[l][r]
        }
        return dp[l][r];
    }
}
class M//矩阵
{
    int l,r; 
    M(int l,int r)
    {
        this.l=l;
        this.r=r;
    }
}

但是很遗憾，提交以后，这题只得了70，还有三组测试组没有通过，觉得会不会是数字太大，改用BigInteger ，不仅超时还内存还超得了40，看样子java感觉不大给力，现在又有考虑转C++了