自底向上的dp

class Solution {


public:

int maxProductAfterCutting(int length) {
    if (length == 0) return 0;
    if (length == 1) return 1;
    if (length == 2) return 1;
    if (length == 3) return 2;
    //int max = 0;
    int dp[length+1];

    memset(dp,0,sizeof(dp));
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 3;
    for (int i=4;i<=length;i++){
        int max = 0;
        for(int j=1; j<=i/2;j++){
            if (dp[i-j] * dp[j] > max){
                max = dp[i-j] *dp[j];
            }
        }
        dp[i] = max;
    }
    // for (int i=0;i<=length;i++)
    //     cout<<dp[i]<<endl;
    return dp[length];
}

};