

典型动归,拆分子问题即可,注意环的问题
f[i][j] = min(f[i][k]+f[k][j]+ a[i]a[j]a[k],f[i][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
|
class Solution { public int minScoreTriangulation(int[] A) {
int n = A.length; int[] a = new int[n*2]; for(int i=0;i<n*2;i++){ a[i] = A[i % n]; } int[][] f = new int[n*2][n*2]; for(int i=0;i<n*2;i++) for(int j=0;j<n*2;j++){ f[i][j] = 50000000; } for(int i=0;i<n*2-1;i++){ f[i][i+1] = 0; } for(int len=3;len<=n;len++) for(int i=0;i<n*2-len+1;i++){ int j= i+len-1; for (int k=i+1;k<j;k++) { f[i][j] = min(f[i][k]+f[k][j]+ a[i]*a[j]*a[k],f[i][j]);
} } int m = 50000000; for(int i=0;i<n;i++){ m = min(m,f[i][i+n-1]); } return m; }
private int min(int a,int b){ if (a>b){ return b; } return a; } }
|
近期评论