问如何使用动态规划来切割长度为n的杆件，从而使其利润最高

EN

 Consider the following example:
 length i   1 2 3 4 5 6 7 8 9 10
 price pi   1 5 8 9 10 17 17 20 24 30

#include <iostream>
#include <stdio.h>
#include <limits.h>

using namespace std;

int max(int a, int b) {return (a > b)? a : b;} 

int cutRod(int price[], int n){
    int r[n+1];
    r[0] = 0; //solution array
    for (int i = 1; i <= n; i++){
        int q = INT_MIN;
        for( int j = 1; j <= i; j++)  {
            q = max(q, price[j-1] + r[i-j]);
            r[i] = q;        
        }
    }
    return r[n];
}

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

    cout << cutRod(price, 1) << endl; 
    cout << cutRod(price, 2) << endl; 
    cout << cutRod(price, 3) << endl; 
    cout << cutRod(price, 4) << endl; 
    cout << cutRod(price, 5) << endl; 
    cout << cutRod(price, 6) << endl;
    cout << cutRod(price, 7) << endl;
    cout << cutRod(price, 8) << endl; 
    cout << cutRod(price, 9) << endl; 
    cout << cutRod(price, 10) << endl; 
    return 0;
}

 1
 5
 8
 10
 13
 17
 20
 24
 30
 32766