题解 | #剪绳子#

1. 一遇到，怎么选的时候，在分析的时候除了把基本的条件出来之后，那紧接着就需要用到递归。
2. 递归会具有很大的时间复杂度，因此要用备忘录的形式剪枝。
3. 其余看注释即可。

class Solution {
public:

    int back_tack(int n, vector<int>& memo){

        if(n<=4){
            return n;
        }

        //带备忘录的递归
        if(memo[n]!=-1){
            return memo[n];
        }


        int res = 0;
        for(int i=1;i<n;i++){
            res = max(res, i*back_tack(n-i,memo));
        }

        //记录当前长度算的最大的成绩
        memo[n] = res;

        return res;

    }


    int cutRope(int number) {

        if(number == 2) return 1;
        if(number == 3) return 2;

        //加一个备忘录

        vector<int> memo(number+1,-1);
        return back_tack(number,memo);

     }
};