ADT - DP(动态规划)

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int Bottom_To_Up_Cut_Rod(vector<int> p, int n) {
        vector<int> r(n);
        r[0] = 0;
        int q = -65533;

        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= i; j++) {
                q = q > (p[j] + r[i - j]) ? q : (p[j] + r[i - j]);
            }
            r[i] = q;
        }

        return r[n];
    }
};

int main() {
    int nums[] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
    int len = (int)sizeof(nums)/sizeof(int);
    vector<int> p(len);
    Solution so;

    for(int i = 0; i < len; i++) {
        p[i] = nums[i];
    }

    cout << "请输入钢材的长度:";
    cin >> len;
    cout << "最大收益为:" << so.Bottom_To_Up_Cut_Rod(p, len) << endl;

    return 0;
}