钢条切割（算法导论）

Serling公司出售一段长度为i英寸的钢条价格为p_i（i=1,2,3...），钢条只能切割为整英寸。

切割问题是这样的，给定一张价格表，和长度为n的原始钢条，求能够产生的最大收益值r_n（可任意整英寸切割或者不切）。

思考：

拿到一根n英寸的钢条，第一刀就有n种切法（最左边表示没切），之后就会变成2条钢条。比如从3的位置切，这样收益就变成了r_n = f(n) = 8+f(n-3)，这样用递归的方式就可以得到结果，递归＋中间结果缓存=动态规划，只不过是自顶向下的方式。还有一种更好的方式是自底向上，类似斐波拉切数列，将子问题按规模排序依次求解。

代码（自顶向下）：

#include <iostream>
#include <vector>

using std::vector, std::cout, std::endl;

class Solution {
private:
    vector<int> memo;

public:
    int do_cut(const vector<int>& tb, int n) {
        auto max = tb.at(n-1);

        // 最小子问题
        if (1 == n) { return tb[0]; }

        for (auto i = 1; i < n; ++i) {
            int sub_max;

            if (0 == memo.at(n-i)) {
                // 缓存子问题结果
                memo[n-i] = sub_max = do_cut(tb, n-i);
            } else {
                sub_max = memo.at(n-i);
            }
            max = std::max(tb.at(i-1) + sub_max, max);
        }

        return max;
    }

    int cut_rod(const vector<int>& tb, int n) {
        memo.resize(tb.size(), 0);

        return do_cut(tb, n);
    }
};

int main() {
    vector<int> prices {1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
    Solution s;

    for (auto i = 1; i < 11; ++i) {
        cout << s.cut_rod(prices, i) << endl;
    }

    return 0;
}

你也可以试试自底向上的方式，留言告诉我。