算法基础 动态规划 钢管问题

Question

类似于这种题目 数据可能有所出入
答案代码如下

#include <iostream>
#include <vector>
#include <algorithm>

int maxProfit(std::vector<int>& price, int n) {
    std::vector<int> dp(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= i; ++j) {
            dp[i] = std::max(dp[i], price[j] + dp[i - j]);
        }
    }
    return dp[n];
}

int main() {
    std::vector<int> price = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30}; // 长度为 i 的钢条的售价
    int n;
    std::cout << "Enter the length of the steel rod: ";
    std::cin >> n;

    int profit = maxProfit(price, n);
    std::cout << "Maximum profit: " << profit << std::endl;

    return 0;
}

那么假如dp[2]>price[2] 那么i=4的钢管的最大值就有可能是两个dp[2] 但是在 dp[i] = std::max(dp[i], price[j] + dp[i - j]);中 并不会出现两个dp[2]相加的情况 那么这个代码是如何保证的得到的dp[4]值一定不小于两个dp[2]之和的呢

Answer 1

引自免费微信小程序：皆我百晓生

在您提供的代码中，dp[i] 表示长度为 i 英寸的钢条通过最优切割策略可以获得的最大利润。对于每个 i（从 1 到 n），代码遍历所有可能的子问题 j（从 1 到 i），尝试将长度为 j 和长度为 i-j 的两部分进行组合，以找到最优的切割策略。

这里的关键在于动态规划的状态转移方程:

dp[i] = std::max(dp[i], price[j] + dp[i - j]);

这个表达式的意思是，当前长度为 i 的钢条的最大利润，要么是之前计算好的结果 dp[i]，要么是选择长度为 j 的钢条并加上剩余长度为 i-j 的钢条的最优利润 dp[i-j]。

虽然在计算 dp[4] 的过程中，每次内层循环只会将 dp[2] 加上 price[2]（即两个长度为 2 英寸的钢条放在一起卖），但请注意，这个过程是在遍历所有可能的 j 值时完成的。这意味着当 j 取 2 时，我们会计算 dp[4] = std::max(dp[4], price[2] + dp[4-2])；而当 j 再次取 2 时，由于外层循环会继续执行，代码会再次检查这个情况，并更新 dp[4]。

这样，在最终计算出的 dp[4] 中，它已经考虑了所有可能的切割方式，包括但不限于将长度为 4 英寸的钢条切成两个长度为 2 英寸的部分。如果这两个长度为 2 英寸的钢条比任何其他组合能带来更大的利润，那么 dp[4] 将自动包含这两个 dp[2] 的总和。因此，这段代码确实能确保得到的 dp[4] 值至少不小于两个 dp[2] 相加的结果。

如果您想看到具体的计算过程，可以逐步跟踪代码运行，观察 dp 数组中的每个元素如何随循环迭代更新。