剑指 Offer 14-I 剪绳子

概述

https://leetcode-cn.com/problems/jian-sheng-zi-lcof/

https://leetcode.com/problems/integer-break/

动态规划法

WA（33 / 50 test cases passed）：

这是因为当输入只有一个且其值较小时，我们的解法会选择不拆开，但是我们最少要拆开一个的。

class Solution {
public:
    int integerBreak(int n) {
        vector<int> store(n + 1, -1);
        store[2] = 1;
        return dp(store, n);
    }
    
    int dp(vector<int>& store, int i) {
        if (store[i] != -1) return store[i];
        int t = i;
        for (int a = 1; a <= i - 1; a++) {
            t = max(t, dp(store, i - a) * dp(store, a));
        }
        store[i] = t;
        return store[i];
    }
};

AC 的解：

可以看到我们硬编码了 n 为 2 和 3 的 case，这是唯一两个其本身的值要比拆开大的。 这种情况的原因在于我们的 dp 函数的要求和题目的要求有些许不一致，即至少拆开两份的要求。

class Solution {
public:
    int integerBreak(int n) {
        if (n == 2) return 1;
        if (n == 3) return 2;
        vector<int> store(n + 1, -1);
        store[2] = 2;
        return dp(store, n);
    }
    
    int dp(vector<int>& store, int i) {
        if (store[i] != -1) return store[i];
        int t = i;
        for (int a = 1; a <= i - 1; a++) {
            t = max(t, dp(store, i - a) * dp(store, a));
        }
        store[i] = t;
        return store[i];
    }
};