Multiplication Puzzle

Multiplication Puzzle"/>

Multiplication Puzzle

题目大致意思是：
一个整数序列包含N个1~100的整数（3<=N<=100），从中取出一个数并和相邻两边的整数相乘，依次进行下去直到只剩下首尾两个数为止，求最终的得到的和的最小值。两边的数不能取，且不重复选取。
这道题代码其实借鉴了某位大神的代码，并做了相应简化更改，
下面说下我从中理解出的思路：
dp[i][j]表示将第I个和第j个之间的数取完得到的和，那么由k表示的数决定的子序列的宽度，依次递增宽度，并且移动子序列，即改变i的值，然后对i到i+k之间的元素进行遍历，比较dp[i][i+k]和先选取a[i]和a[j]之间的数，a[j]和a[i+k]之间的数，最后只剩下a[j]，这一过程中的得到的和dp[i][j]+dp[j][i+k]+a[i]*a[i+k]*a[j]与原来的和的大小。

#include<stdio.h>
#include<string.h>
#define min(a,b) ((a)<(b)?(a):(b))
int dp[110][110];
int main(void)
{int i,j,k,a[110];int n;scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);for(k=2;k<=n;k++)for(i=1;i+k<=n;i++){dp[i][i+k]=10000000;设dp[i][k+i]的初值很大，for(j=i+1;j<i+k;j++)dp[i][i+k]=min(dp[i][i+k],dp[i][j]+dp[j][i+k]+a[i]*a[i+k]*a[j]);}printf("%d\n",dp[1][n]);return 0;
}