爆搜
blablab
class Solution {
public:
int ans=0;
unordered_map<int,int>g;
int maxProductAfterCutting(int length) {
dfs(length,0);
return ans;
}
//n为剩余
void dfs(int n,int cur)
{
if(n==0||n==1){
ans=max(ans,cur);
return ;
}
if(cur&&cur<=g[n]){return;}
g[n]=max(g[n],cur);
//i为下一段
for(int i=cur==0?n-1:n;i>=1;i--)
{
dfs(n-i,cur==0?i:cur*i);
}
}
};
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla