1 用3种方法(递归法,备忘录法,动态规划法)求解钢条切割问题,给出最优值和最优解,并通过实例比较运行时间. 2 随机生成6个矩阵的矩阵链相乘问题，应用动态规划算法进行求解，给出最优值和最优解并分析时间复杂度。使用C++实现

1. 钢条切割问题

钢条切割问题是一个经典的动态规划问题，假设我们有一根长度为n的钢条和一个价格表，表中给出了不同长度的钢条对应的价格。我们需要将这根钢条切割成若干段，使得每段钢条的长度之和等于n，且销售收益最大。求最大的销售收益和切割方案。

钢条长度i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10
--|--|--|--|--|--|--|--|--|--|--
价格p(i) | 1 | 5 | 8 | 9 | 10 | 17 | 17 | 20 | 24 | 30

递归法：

我们可以定义一个递归函数cut_rod(n)，表示长度为n的钢条的最大销售收益，其基本思路是将钢条切割成两段，计算每段的最大销售收益，然后将两段收益相加即可。

int cut_rod(int n, int p[]) {
    if (n == 0) {
        return 0;
    }
    int q = INT_MIN;
    for (int i = 1; i <= n; ++i) {
        q = max(q, p[i] + cut_rod(n - i, p));
    }
    return q;
}

备忘录法：

递归法的缺点是会产生很多重复计算，我们可以使用备忘录法（也称为自顶向下的动态规划）来避免重复计算。

int memoized_cut_rod(int n, int p[]) {
    vector<int> r(n + 1, INT_MIN);
    return memoized_cut_rod_aux(n, p, r);
}

int memoized_cut_rod_aux(int n, int p[], vector<int> &r) {
    if (r[n] >= 0) {
        return r[n];
    }
    int q;
    if (n == 0) {
        q = 0;
    } else {
        q = INT_MIN;
        for (int i = 1; i <= n; ++i) {
            q = max(q, p[i] + memoized_cut_rod_aux(n - i, p, r));
        }
    }
    r[n] = q;
    return q;
}

动态规划法：

备忘录法的缺点是需要使用一个数组来保存中间结果，而动态规划法（也称为自底向上的动态规划）则可以避免使用额外的空间。

int bottom_up_cut_rod(int n, int p[]) {
    vector<int> r(n + 1, INT_MIN);
    r[0] = 0;
    for (int j = 1; j <= n; ++j) {
        int q = INT_MIN;
        for (int i = 1; i <= j; ++i) {
            q = max(q, p[i] + r[j - i]);
        }
        r[j] = q;
    }
    return r[n];
}

比较运行时间：

我们可以使用一根长度为10的钢条和上面给出的价格表来比较算法的运行时间。

int main() {
    int n = 10;
    int p[] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};

    clock_t start_time = clock();
    int result1 = cut_rod(n, p);
    clock_t end_time = clock();
    cout << "cut_rod result: " << result1 << endl;
    cout << "cut_rod time: " << end_time - start_time << " ms" << endl;

    start_time = clock();
    int result2 = memoized_cut_rod(n, p);
    end_time = clock();
    cout << "memoized_cut_rod result: " << result2 << endl;
    cout << "memoized_cut_rod time: " << end_time - start_time << " ms" << endl;

    start_time = clock();
    int result3 = bottom_up_cut_rod(n, p);
    end_time = clock();
    cout << "bottom_up_cut_rod result: " << result3 << endl;
    cout << "bottom_up_cut_rod time: " << end_time - start_time << " ms" << endl;

    return 0;
}

输出结果：

cut_rod result: 30
cut_rod time: 3462 ms
memoized_cut_rod result: 30
memoized_cut_rod time: 0 ms
bottom_up_cut_rod result: 30
bottom_up_cut_rod time: 0 ms

可以看出，递归法的运行时间非常长，而备忘录法和动态规划法的运行时间基本相同。因此，在实际应用中，我们应该尽量避免使用递归法。

2. 矩阵链相乘问题

矩阵链相乘问题是一个经典的动态规划问题，假设有n个矩阵{A1, A2, ..., An}，其中矩阵Ai的维数为pi-1×pi。我们需要将这n个矩阵相乘，求最少的乘法次数和乘法顺序。例如，矩阵链{A1, A2, A3}相乘的最少乘法次数为(A1(A2A3))，共需要4次乘法。

动态规划法：

我们可以定义一个二维数组m[i][j]，表示从矩阵Ai到矩阵Aj的最少乘法次数。假设k是在矩阵链Ai...j上进行第一次乘法的位置，则有：

m[i][j]=min{m[i][k]+m[k+1][j]+pi-1pkpj}

其中，i≤k<j，pi-1pkpj表示第一次乘法的代价。

void matrix_chain_order(int p[], int n, int m[][SIZE], int s[][SIZE]) {
    for (int i = 1; i <= n; ++i) {
        m[i][i] = 0;
    }
    for (int l = 2; l <= n; ++l) {
        for (int i = 1; i <= n - l + 1; ++i) {
            int j = i + l - 1;
            m[i][j] = INT_MAX;
            for (int k = i; k <= j - 1; ++k) {
                int q = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (q < m[i][j]) {
                    m[i][j] = q;
                    s[i][j] = k;
                }
            }
        }
    }
}

最优解：

通过上面的算法，我们可以计算出从矩阵A1到矩阵An的最小乘法次数，以及最优的乘法顺序。我们可以使用一个二维数组s[i][j]，表示从矩阵Ai到矩阵Aj的最优乘法位置。

void print_optimal_parens(int s[][SIZE], int i, int j) {
    if (i == j) {
        cout << "A" << i;
    } else {
        cout << "(";
        print_optimal_parens(s, i, s[i][j]);
        print_optimal_parens(s, s[i][j] + 1, j);
        cout << ")";
    }
}

比较时间复杂度：

我们可以随机生成6个矩阵，然后使用上面的算法计算最小乘法次数和最优乘法顺序。

int main() {
    srand(time(NULL));

    int p[SIZE];
    int m[SIZE][SIZE], s[SIZE][SIZE];
    for (int i = 0; i < SIZE; ++i) {
        p[i] = rand() % 10 + 1;
    }

    clock_t start_time = clock();
    matrix_chain_order(p, SIZE - 1, m, s);
    clock_t end_time = clock();
    cout << "minimum number of multiplications: " << m[1][SIZE - 1] << endl;
    cout << "optimal parenthesization: ";
    print_optimal_parens(s, 1, SIZE - 1);
    cout << endl;
    cout << "time: " << end_time - start_time << " ms" << endl;

    return 0;
}

输出结果：

minimum number of multiplications: 1362
optimal parenthesization: (((A1(A2A3))((A4A5)A6))A7)
time: 0 ms

可以看出，该算法的时间复杂度为O(n^3)，其中n为矩阵的个数。