ALDS1_10_B Matrix Chain Multiplication

問題
連鎖行列積 | アルゴリズムとデータ構造 | Aizu Online Judge

行列の掛け算は、掛ける順番が異なると計算回数が変わります。
例えばA:10*5 B:5*8 C:8*20の行列があり、この積ABCを考えると
(AB)C=10*5*8+10*8*20=2000(回)
A(BC)=5*8*20+10*5*20=1800(回)
このようになります。今回の問題は、与えられた行列の積を求めるのに、計算回数が最小となる場合の計算回数を求める問題です。

動的計画法で求めます。dp[i][j]を「i番目からj番目の行列の積を求めるのに必要な最小の計算回数」とします。
そんでdp[i][j]=dp[i][k]+dp[k+1][j]+Ri*Ck*Cjとなります（i=jのときは0）

import java.util.Scanner;

class alds_10_b{
	
	static int getAns(int[] r,int[] c,int n){
		int[][] dp=new int[n][n];
		
		for(int i=0;i<n;i++)
			for(int j=i;j<n;j++)
				dp[i][j]=Integer.MAX_VALUE;
		
		
		int i=0; int j=0;
		
		for(int sj=0;sj<n;sj++){
			i=0; j=sj;
			for(int k=0;k<n-sj;k++){
				if(i==j)
					dp[i][j]=0;
				else{
					for(int m=i;m<j;m++){
						dp[i][j]=Math.min(dp[i][j],dp[i][m]+dp[m+1][j]+r[i]*c[m]*c[j]);
					}
				}
				i++; j++;
			}
		}
		
		
		return dp[0][n-1];
	}
				
	
	public static void main(String[] args){
		Scanner scan=new Scanner(System.in);
		
		int n=scan.nextInt();
		int[] r=new int[n];
		int[] c=new int[n];
		
		for(int i=0;i<n;i++){
			r[i]=scan.nextInt();
			c[i]=scan.nextInt();
		}
		
		System.out.println(getAns(r,c,n));
		
	}
}