面试题 14- I. 剪绳子

题目描述

给你一根长度为 n 的绳子,请把绳子剪成整数长度的 m 段(m、n都是整数,n>1并且m>1),每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0] * k[1] *...* k[m-1] 可能的最大乘积是多少?

示例

例如,当绳子的长度是8时,我们把它剪成长度分别为2、3、3的三段,此时得到的最大乘积是18。

题解

class Solution {
public:
    int integerBreak(int n) {
        vector<int> table(n + 1, 0);
        table[2] = 1;
        for (int i = 3; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                table[i] = max({table[i], j * (i - j), j * table[i - j]});
            }
        }
        return table[n];
    }
};

相关推荐

  1. 面试 14- I. 绳子

    2024-07-09 18:22:02       10 阅读
  2. 算法:绳子

    2024-07-09 18:22:02       38 阅读
  3. Redis面试14

    2024-07-09 18:22:02       38 阅读
  4. 面试经典150(14)

    2024-07-09 18:22:02       43 阅读
  5. 14. Tomcat面试汇总

    2024-07-09 18:22:02       20 阅读
  6. Redis面试10

    2024-07-09 18:22:02       37 阅读
  7. Redis面试13

    2024-07-09 18:22:02       33 阅读
  8. Redis面试12

    2024-07-09 18:22:02       37 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-09 18:22:02       3 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-09 18:22:02       3 阅读
  3. 在Django里面运行非项目文件

    2024-07-09 18:22:02       2 阅读
  4. Python语言-面向对象

    2024-07-09 18:22:02       2 阅读

热门阅读

  1. 机器学习 - 比较检验

    2024-07-09 18:22:02       8 阅读
  2. Mac OS系统中Beyond Compare 4破解方式

    2024-07-09 18:22:02       9 阅读
  3. Mongodb索引的创建与命名

    2024-07-09 18:22:02       9 阅读
  4. 搭建纯净的SpringBoot工程

    2024-07-09 18:22:02       11 阅读
  5. 新型开发语言的试用感受-仓颉语言发布之际

    2024-07-09 18:22:02       16 阅读
  6. ubuntu 如何解压tar

    2024-07-09 18:22:02       10 阅读
  7. VScode 常用插件

    2024-07-09 18:22:02       10 阅读
  8. 站群服务器与普通服务器之间的区别

    2024-07-09 18:22:02       11 阅读
  9. 怎么区分服务器的硬盘是ssd还是hdd?

    2024-07-09 18:22:02       10 阅读
  10. RedHat运维-Linux文件管理基础2-ls与find

    2024-07-09 18:22:02       10 阅读