题解 | #剪绳子#

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int cutRope(int n) {
        /**
         * f(1) = 1
         * f(2) = 1
         * f(3) = 2
         * f(4) = max(f(4-x), f(x))
         */
         if (n == 0) return 0;
         if (n == 1) return 1;
         if (n == 2) return 2;
         if (n == 3) return 3;

         vector<int> f(n+1);
         f[0] = 0;
         f[1] = 1;
         f[2] = 2;
         f[3] = 3;

         int max = 0;
         for (int x = 4; x <= n; x++) {
            max = 0;
            // y = f(x)
            for (int i = 1; i <= x/2; ++i) {
                int y = f[i] * f[x-i];
                max = max > y ? max : y;
            }
            f[x] = max;
         }
         max = f[n];

         return max;
        

         return 0;
    }
};

这种动态规划的题

先提炼递推公式：

y = f(x) , x表示绳子的长度, y代表绳子切割后的最大值

f(0) = 0

f(1) = 1

f(2) = 2 # 不需要剪去

f(3) = 3 # 不需要剪去

f(4) = max{ f(1) * f(3),

f(2} * f(2)，

f(3) * f(1)}

f(5) = max{ f(1) * f(4),

f(2) * f(3),

f(3) * f(2),

f(4) * f(1)}

....

从 f4,f5 的推导可以看出这应该是一个遍历循环的过程，因此内部需要遍历找出 max

由于绳子是剪成两段，因此只要长度过半，就不需要再遍历了，

所以 循环遍历终止的条件是 n/2