题解 | #剪绳子#
剪绳子
https://www.nowcoder.com/practice/57d85990ba5b440ab888fc72b0751bf8
#include <vector>
class Solution {
public:
// int max(vector<int> &dp,int l)
// {
// int max = 0;
// for(int i = 1;i <= l/2;i++)
// max = max > (dp[i] * dp[l-i]) ? max : (dp[i] * dp[l-i]);
// return max;
// }
int cutRope(int number) {
if(number <= 1)
return 0;
if(number < 4)
return number - 1;
vector<int> dp(60,0);
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
int m;
for(int i = 4;i <= number;i++)
{
m = 0;
for(int j = 1;j <= i/2;j++)
m = max(m,dp[j] * dp[i-j]);
dp[i] = m;
}
//dp[i] = max(dp,i);
return dp[number];
}
};
查看8道真题和解析
投递牛客等公司10个岗位 >
