【动态规划】插入乘号问题

问题描述： 给出 N N N 个 1 1 1 - 9 9 9 的数字 ( v 1 , v 2 , … , v N ) (v1,v2,…,vN) (v1,v2,…,vN)，不改变它们的相对位置，在中间加入 K K K 个乘号和 N − K − 1 N-K-1 N−K−1 个加号，括号随便加，使最终结果最大。因为乘号和加号一共就是 N − 1 N-1 N−1 个，所以恰好每两个相邻数字之间都有一个符号。 例如： N = 5 N=5 N=5, K = 2 K=2 K=2， 5 5 5 个数字分别为 1 1 1、 2 2 2、 3 3 3、 4 4 4、 5 5 5，可以进行如下运算： 1 ∗ 2 ∗ ( 3 + 4 + 5 ) = 24 1*2*(3+4+5)=24 1∗2∗(3+4+5)=24 1 ∗ ( 2 + 3 ) ∗ ( 4 + 5 ) = 45 1*(2+3)*(4+5)=45 1∗(2+3)∗(4+5)=45 ( 1 ∗ 2 + 3 ) ∗ ( 4 + 5 ) = 45 (1*2+3)*(4+5)=45 (1∗2+3)∗(4+5)=45 等等.

思路： 例如在计算 N = 5 N=5 N=5, K = 2 K=2 K=2 时，我们可以通过计算 m a x [ 0 ] [ 0 ] ∗ ( 2 + 3 + 4 + 5 ) max[0][0]*(2+3+4+5) max[0][0]∗(2+3+4+5)、 m a x [ 0 ] [ 1 ] ∗ ( 3 + 4 + 5 ) max[0][1]*(3+4+5) max[0][1]∗(3+4+5)、 m a x [ 0 ] [ 2 ] ∗ ( 4 + 5 ) max[0][2]*(4+5) max[0][2]∗(4+5)、 m a x [ 0 ] [ 3 ] ∗ ( 5 ) max[0][3]*(5) max[0][3]∗(5)等等这些式子的最大值得到最终的结果，这样就建立起了动态规划的思路。 状态转移方程已经体现在代码之中了。

源代码：

//
//  main.cpp
//  InsertMultiplier
//
//  Created by 胡昱 on 2022/1/5.
//

#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

// 数字数量及其最大值
int n;
const int MAX_N = 20;

// 乘号数量及其最大值
int k;
const int MAX_K = MAX_N - 1;

// 存储数字数组
int digits[MAX_N];

// 动态规划数组，dp[i][j]表示从第0个数字到第i个数字中插入j个乘号时所得到的最大值
long long dp[MAX_N][MAX_N];

// 累加数组，sum[i][j]代表了从第i个数字到第j个数字累加的结果
long long sum[MAX_N][MAX_N];


int main(int argc, const char * argv[]) {
          
   
    // 共M组测试用例
    int M;
    cin >> M;
    while((M--) > 0) {
          
   
        // 初始化（其实感觉不用初始化也可以）
        memset(digits, 0, sizeof(digits));
        memset(dp, 0, sizeof(dp));
        memset(sum, 0, sizeof(sum));
        
        // 输入数字数量n和乘号个数k
        cin >> n >> k;
        
        // 输入数字
        for(int ni = 0; ni < n; ++ni) {
          
   
            cin >> digits[ni];
        }
        
        // 初始化累加数组
        for(int ni = 0; ni < n; ++ni) {
          
   
            long long temp = 0;
            for(int nj = ni; nj < n; ++nj) {
          
   
                temp += digits[nj];
                sum[ni][nj] = temp;
            }
        }
        
        // 初始化动态规划数组（插入乘号数量为0时就等于一直累加）
        for(int ni = 0; ni < n; ++ni) {
          
   
            dp[ni][0] = sum[0][ni];
        }
        
        // 开始动态规划
        // 递推式挺好理解的，也就是取后面累加的值和前面某一段的最大值的乘积的最大值
        for(int ni = 0; ni < n; ++ni) {
          
   
            // 插入的乘号数量不仅要小于等于k，还要小于当前数字数量
            for(int ki = 1; ki <= k && ki <= ni; ++ki) {
          
   
                for(int nj = 0; nj < ni; ++nj) {
          
   
                    dp[ni][ki] = max(dp[nj][ki - 1] * sum[nj + 1][ni], dp[ni][ki]);
                }
            }
        }
        
        // 输出结果
        cout << dp[n - 1][k] << endl;
    }
    return 0;
}