题解 | #剪绳子#

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

class Solution {
public:
    int cutRope(int n) {
        //只存在一种情况得直接输出了
        if(n == 2) return 1;
        if(n == 3) return 2;
        vector<int> vec(61,0);
        //这几种情况要么不满足题目要求：0和1，要么就是上面只有一种情况输出了，所以可以填不切一刀的最大值
        vec[0] = 0;
        vec[1] = 1;
        vec[2] = 2;
        vec[3] = 3;
        for(int i = 4;i <= n;i ++){
            int max = 0;
            //j不用取0，因为只要一段是0的话，乘下来就是0了。
            for(int j = 1;j <= i / 2;j ++){
                //取最大值即可，找到当长度为i时切割的最佳方案。
                if(j * vec[i - j] > max) max = j * vec[i - j];
            }
            vec[i] = max;
        }
        return vec[n];
    }
};
// 64 位输出请用 printf("%lld")