最優(yōu)矩陣鏈乘：

一個n*m的矩陣乘一個m*p的矩陣等于一個n*p的矩陣，運算量為mnp，現在有一組n個矩陣組成的序列，求運算量的最小值。

這是DP中的最優(yōu)矩陣鏈乘問題，我們可以這么理解：用一個d[i][j]來存儲第i個矩陣鏈乘到第j個矩陣的最優(yōu)解，那么現在進行DP化，也就是找它的子解。我們把這組序列從中間不同位置裂開，記這個位置為k，那么不難得到d[i][j]=d[i][k]+d[k+1][j]+p[i-1]*p[k]*p[j]，根據最優(yōu)化原則，如果d[i][k]和d[k+1][j]都已經是最優(yōu)解，那么我們只要取k為某值時d[i][j]為最小即可。

可以寫出狀態(tài)轉移方程：d[i][j] = min(d[i][j], d[i][k] + d[k + 1][j] + p[i - 1] * p[k] * p[j])，但要注意，這里如果用遞推，i和j都是很難取的，因為這按i和j的區(qū)間遞推的，所以我們按照j-i遞增的順序遞推，長區(qū)間的值依賴與小區(qū)間的值。邊界條件是d[i][i]=0。

#include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> using namespace std; int n; int d[105][105],p[105];int main() {int i, j,k,l;while (~scanf("%d", &n)){for (i = 1; i <= n; i++)scanf("%d%d", &p[i - 1], &p[i]);for (i = 1; i <= n; i++)d[i][i] = 0;for (l = 2; l <= n; l++)//按照j-i也就是區(qū)間的長度來遞推{for (i = 1; i <= n - l + 1; i++){j = i + l - 1;d[i][j] = 0xfffffff;for (k = i; k <= j - 1; k++)d[i][j] = min(d[i][j], d[i][k] + d[k + 1][j] + p[i - 1] * p[k] * p[j]);}}printf("%d\n", d[1][n]);}return 0; }

最優(yōu)三角剖分：

對于一個n個頂點的凸三角形，用n-3條互不相交的對角線將其分成n-2個三角形，為每個三角形規(guī)定一個權函數w(i,k,j)（三角形的周長），求讓所以三角形權值和最小的值。 還是區(qū)間DP的原理，從區(qū)間中找k，切出一個三角形和兩個子多邊形，進行DP即可，注意這里的邊界為d[i][i]=d[i][i+1]=0。 狀態(tài)轉移方程為：d[i][j] = min(d[i][j], d[i][k] + d[k][j] + w(i, k, j))，i<k<j。 #include<stdio.h> #include<stdlib.h> #include<string.h> #include<algorithm> using namespace std; const int n = 6; int w[][n] = { { 0,2,2,3,1,4 },{ 2,0,1,5,2,3 },{ 2,1,0,2,1,4 },{ 3,5,2,0,6,2 },{ 1,2,1,6,0,1 },{ 4,3,4,2,1,0 } }; int d[10][10];int get_weight(int a, int b, int c) {return (w[a][b] + w[a][c] + w[b][c]); }int main() {int i, j, l, k;for (i = 0; i <= n; i++)//邊界條件{d[i][i] = 0;d[i][i + 1] = 0;}for (l = 2; l < n; l++){for (i = 0; i + l <= n-1; i++){j = i + l;d[i][j] = 0xffffff;for (k = i + 1; k < j; k++)d[i][j] = min(d[i][j], d[i][k] + d[k][j] + get_weight(i, k, j));}}printf("%d\n", d[0][n - 1]);return 0; }

轉載于:https://www.cnblogs.com/seasonal/p/10343738.html

總結

以上是生活随笔為你收集整理的DP——最优矩阵链乘最优三角剖分的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。