|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 糖逗 于 2020-5-8 17:42 编辑
题目描述:
- 给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]...k[m] 。请问 k[0]*k[1]*...*k[m] 可能的最大乘积是多少?例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。
- 示例 1:
- 输入: 2
- 输出: 1
- 解释: 2 = 1 + 1, 1 × 1 = 1
- 示例 2:
- 输入: 10
- 输出: 36
- 解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
- 提示:
- 2 <= n <= 58
- 来源:力扣(LeetCode)
- 链接:https://leetcode-cn.com/problems/jian-sheng-zi-lcof
- 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码
- #include<iostream>
- using namespace std;
- int solution(int input){
- int dp[60] = {0};
- dp[0] = 0;
- dp[1] = 1;
- dp[2] = 1;
- for(int i = 3; i <= input; i++){
- for(int j = 0; j < i; j++){
- dp[i] = max(dp[i], max(j*(i-j), j*dp[i-j]));
- }
- }
- return dp[input];
- }
- int main(void){
- int input;
- cin >> input;
- int res = solution(input);
- cout << res << endl;
- return 0;
- }
复制代码
注意事项:
1.动态规划。
2.参考链接:https://leetcode-cn.com/problems ... a-ji-zhu-dong-tai-/ |
|