lintcode 700. 杆子分割 完全背包

杆子分割 完全背包"/>

lintcode 700. 杆子分割 完全背包

给一个 n 英寸长的杆子和一个包含所有小于 n 的尺寸的价格. 确定通过切割杆并销售碎片可获得的最大值.

样例
样例1输入：
[1, 5, 8, 9, 10, 17, 17, 20]
8
输出：22
解释：
长度    | 1   2   3   4   5   6   7   8  
--------------------------------------------
价格    | 1   5   8   9  10  17  17  20
切成长度为 2 和 6 的两段。
样例2输入：
[3, 5, 8, 9, 10, 17, 17, 20]
8
输出：24
解释：
长度    | 1   2   3   4   5   6   7   8  
--------------------------------------------
价格    | 3   5   8   9  10  17  17  20
切成长度为 1 的 8 段。

思路：计算每一种方案把杆子切割完后的最大值即可

class Solution {
public:/*** @param prices: the prices* @param n: the length of rod* @return: the max value*/int cutting(vector<int> &prices, int n) {// Write your code herevector<int> dp(n+1,0);for (int i = 1; i <= prices.size(); i++) {for(int j = i; j <=n;j++){dp[j]=max(dp[j],dp[j-i]+prices[i-1]);}}return dp[n];}
};