剑指 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];
}
};
Links: sword-offer-14-1