poj 1651 Multiplication Puzzle

简单DP，矩阵相乘，这次尝试自己写一个，居然过了，很好。本来今天还水了poj 1088 二维空间最长下降（上升）序列和 poj 3624 超水0，1背包，也想贴出来凑数的，可是zxpn同志说，这么水的题你也好意思贴出来，只好做罢。

 1 #include <stdio.h>
 2 #include <string.h>
 3 int f[100][100],a[105];
 4 int dp(int i,int j)
 5 {
 6     int k, min, &ans = f[i][j];
 7     if(f[i][j] != -1)
 8         return ans;
 9     if(i == j)
10         return ans = 0;
11     min = 1<<30;
12     for(k = i; k < j; k++)
13     {
14         int t = dp(i,k)+dp(k+1,j)+a[i-1]*a[k]*a[j];
15         if(t < min) min = t;
16     }
17     return ans = min;
18 }
19 int main()
20 {
21     int n;
22     while(~scanf("%d",&n))
23     {
24         for(int i = 0; i < n; i++)
25             scanf("%d",&a[i]);
26         memset(f,-1,sizeof(f));
27         printf("%d\n",dp(1,n-1));
28     }
29     return 0;
30 }