HDU - 5396 Expression

题目大意：
给你一个n然后是n个数。 然后是n-1个操作符，操作符是插入在两个数字之间的。 由于你不同的运算顺序，会产生不同的结果。
比如：
1 + 1 * 2 有两种 （1+1）*2 或者 1+（1*2）
1 * 2 * 3 也是两种即使结果是一样的 （1*2）3 或者 1（2*3）
问这所有不同的组合加起来的和对 1e9+7取余是多少。

解题思路：
这个其实就是区间DP了
dp[i][j] 代表的是区间 i 到 j 的和
枚举dp[i][j] 之间所有的子区间
假如是乘法：
t = dp[i][k] * dp[k+1][j]；
这个其实可以直接算出来的：
假设我们dp[i][k] 里面所有的值是 （x1+x2+x3…xn） == dp[i][k]
假设我们dp[k+1][j] 里面所有的值是 （y1+y2+y3…yn） == dp[k+1][j]
dp[i][k] * dp[k+1][j] == (x1+x2+…xn) * (y1+y2+y3…yn) == x1*y1+x1y*y2……xn*yn 其实和所有不同结果相乘出来是一样的

假如是加法或者减法：
我们表示阶乘 i为A[i].
t = dp[i][k]*A[j-k-1] + dp[k+1][j]*A[k-i];
其实这里我们想一下。区间 dp[i][k] 需要加上多少次？
我们需要加的次数就是另一半区间的所有组合数，另一半区间有多少种组合方式我们就要加上多少个。
因为他们之间可以相互组成不同的种类。同理另一半也是。

最后的时候我们要乘上一个组合数。
假设组合数为C[i][j].
为什么要乘组合数：
因为 假如我们k 分割了两个运算式子 【 1+（2*3） 】 + 【 1+（3*4） 】
虽然说我们左右两边的式子运算顺序已经确定了，但是我们总的运算顺序还是不确定的， 比如我们算完（2*3） 直接去算（3*4）也是不同的结果
dp[i][j] = dp[i][j] + t*C[j-i-1][k-i]
这个其实就是从总的运算符(j-i-1)（减去了第k个的运算符）个中选取(k-i)个进行运算。
因为我们选取数达到 k-i的时候，另外我们还需要保持左右两边运算的相对顺序。
就比如说：左边有a 个运算符， 右边有b个运算符。
我们从 a+b个位置中选取 a位置个放a个的运算符。其余的只能放另一边的的运算符了。因为我们左右两边的相对顺序是不变的。

#include <cstdio>

int main() {
    const long long MOD = 1e9 + 7;
    long long C[105][105]; 
    for (int i = 0; i <= 100; i++)
        C[i][0] = 1;
    for (int i = 1; i <= 100; i++)
        for (int j = 1; j <= i; j++) 
            C[i][j] = (C[i-1][j] + C[i-1][j-1]) % MOD;

    long long F[105] = {1};
    for (int i = 1; i <= 100; i++) 
        F[i] = (i * F[i-1]) % MOD;

    int n;
    char op[105];
    while (scanf("%d", &n) != EOF) {
        long long DP[105][105] = {0};
        for (int i = 1; i <= n; i++)
            scanf("%lld", &DP[i][i]);
        scanf("%s", op + 1);

        for (int l = 1; l <= n-1; l++)
            for (int i = 1; i <= n-l; i++){
                int j = i + l;
                for (int k = i; k < j; k++) {
                    long long tmp = 0;
                    if (op[k] == ‘*‘)
                        tmp = (DP[i][k] * DP[k+1][j]) % MOD; 
                    else if (op[k] == ‘+‘)
                        tmp = (F[j-k-1] * DP[i][k] + F[k-i] * DP[k+1][j]) % MOD;
                    else
                        tmp = (F[j-k-1] * DP[i][k] - F[k-i] * DP[k+1][j]) % MOD;

                    DP[i][j] = (DP[i][j] + tmp * C[j-i-1][k-i]) % MOD;
                }
            }
        printf("%lld\n", (DP[1][n] + MOD) % MOD);
    }

    return 0;
}