POJ - 1651 Multiplication Puzzle(区间dp)

题目大意：给你N个数，每次可以选择一个数进行剔除(第一个和最后一个不能选择)，选出该数后，sum += 该数左边的数 ＊ 该数 ＊ 该数右边的数
问最小的sum是多少

解题思路：用dp[i][j]表示[i,j]区间被剔除得只剩下i，j的最小sum
dp[i][j] = dp[i][k] + dp[k][j] + num[i] * num[k] * num[j]

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;

int dp[N][N], num[N];
int n;
void solve() {
    memset(dp, 0, sizeof(dp));

    for (int i = 0; i < n - 2; i++)
        dp[i][i + 2] = num[i] * num[i + 1] * num[i + 2];

    for (int len = 3; len < n; len++) {
        for (int i = 0; i + len < n; i++) {
            int j = i + len;
            for (int k = i + 1; k < j; k++)
                if (dp[i][j] == 0) 
                    dp[i][j] = dp[i][k] + dp[k][j] + num[k] * num[i] * num[j];
                else 
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + num[k] * num[i] * num[j]);
        }
    }
    printf("%d\n", dp[0][n - 1]);
}

int main() {
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++)
            scanf("%d", &num[i]);
        solve();
    }
    return 0;
}