LeetCode343.整数拆分
今天在哔哩哔哩上刷到了一个非常有意思的leetcode整数拆分的题，博主利用动态规划。我暂时没有想到动态规划来求解，因此先尝试一下记忆性递归，没想到击败100%用户，暂时不清楚leetcode屏蔽逻辑。该题并不是很难，但有一个递归技巧点，因此进行记录。
class Solution {
public int integerBreak(int n) {
return integerBreakBy(n, new int[n], true);
}
public int integerBreakBy(int i, int[] data, boolean flag){
if(i <= 1){
return 1;
}
int max = -1;
int a = flag ? i - 1 : i;
for(int j = 1; j <= a; j++){
int i_j = 0;
if(data[i - j] == 0)
data[i - j] = integerBreakBy(i - j, data, false);
int cur_data = j * data[i - j];
max = max < cur_data ? cur_data : max;
}
return max;
}
}
由于该题解要求拆出的数字个数要大于1，但是在子递归中，不用进行拆分就也是可以的，因此，引入了一个flag参数，当第一次进行拆分的时候，只要拆分出两个，子问题没有这条限制，所以引入了一个flag。