题解 | #剪绳子#

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
     //方法1：动态规划
     /*
     特点：求最优解 + 问题可以分解 + 子问题出现递归分解 + 子问题有重复出现
     解法：自上而下分析，自下而上计算。从最小的子问题计算，保存计算结果，一步步迭代到目标。
     */
    // int cutRope(int n) {
    //     vector<int> maxVec ;
    //     maxVec.push_back(0);
    //     maxVec.push_back(1);
    //     maxVec.push_back(2);
    //     maxVec.push_back(3);
    //     maxVec.push_back(4);
    //     if(n<=4){
    //         return maxVec[n];
    //     }
    //     for(int i=5;i<=n;i++){
    //         int tempMax = 0;
    //         int mul = 0;
    //         for(int j=1;j<=i/2;j++){
    //             mul  =maxVec[j] * maxVec[i-j];
    //             if(mul>tempMax) tempMax = mul;
    //         }
    //         maxVec.push_back(tempMax);
    //     }
    //     return maxVec[n];
    // }

    //方法2：贪心算法
     /*
     特点：求最优解 + 问题可以分解 + 子问题出现递归分解 + 子问题有重复出现
     解法：有一定数学证明。本题就是小于5时每次减3。
     */
     int cutRope(int n) {
        int res=1;
        while(n>=5){
            res *=3;
            n -=3;
        }
        return res*n;
     }

};