230123 최적의 행렬 곱셉

public static int solution(int[][] matrixSizes) {
	int length = matrixSizes.length;
	int[][] dp = new int[length][length];
	
	for(int i = 0; i < length; i++){
		for(int j = 0; j < length; j++){
			dp[i][j] = Integer.MAX_VALUE;
		}
	}
	
	for(int i = 0; i < length; i++){
		for(int j = 0; j < length-i; j++){
			int a = j;
			int b = j+i;
			if(a == b) dp[a][b] = 0;
			else{
				for(int k = a; k < b; k++){
					dp[a][b] = Math.min(dp[a][b], dp[a][k] + dp[k+1][b] + matrixSizes[a][0] * matrixSizes[k][1] * matrixSizes[b][1]);
				}
			}
		}
	}
	
	return dp[0][length-1];
}

행렬의 최적 곱셈 방법을 찾기 위해서 먼저 dp행렬에 큰 값을 넣어주고 점화식에 따라 최솟값을 찾아줌

• 한번에 계산하는 것과 나누어 계산(결합)하였을때의 값을 비교

dp[a][b], dp[a][k] + dp[k+1][b] + matrixSizes[a][0] * matrixSizes[k][1] * matrixSizes[b][1]);