POJ 1651 Multiplication Puzzle 區間dp（水

POJ 1651 Multiplication Puzzle 區間dp（水

題目鏈接：點擊打開鏈

題意：

給定一個數組，每次可以選擇內部的一個數 i 消除，獲得的價值就是 a[i-1] * a[i] * a[i+1]

問最小價值

思路：

dp[l,r] = min( dp[l, i] + dp[i, r] + a[l] * a[i] * a[r]);

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N = 105;
const int inf = 100000000;
int a[N], dp[N][N], n;
int dfs(int l, int r){//返回 把區間l,r合並，最後只剩下a[l]和a[r]能獲得的最小價值
    if(l > r) return 0;
    if(dp[l][r] != -1)return dp[l][r];//若區間[l,r]已經計算過則不再計算
    if(l == r || l+1 == r) return dp[l][r] = 0;//只有1個或者2個元素則價值是0
    int ans = inf;
    for(int i = l+1; i < r; i++)
        ans = min(ans, a[i] * a[l] * a[r] + dfs(l, i) + dfs(i, r));

    return dp[l][r] = ans;
}
int main(){
    while(cin>>n){
        for(int i = 1; i <= n; i++)scanf("%d", &a[i]);
        memset(dp, -1, sizeof dp);
        cout<