题解 | #剪绳子#

剪绳子

https://www.nowcoder.com/practice/57d85990ba5b440ab888fc72b0751bf8

#include <vector>
class Solution {
public:
	// 动态规划,保存上一次计算结果
    int cutRope(int n) {
        // write code here
        vector<int> dp(n+1,0);  // 初始化n+1元素意思,每个初始化为0;n+1,目的保证下标对齐绳子长度
        // vector<int> dpp{n+1,0};// 添加两个元素意思
        // std::cout << dp.size() <<" " << dpp.size() << std::endl;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 4;
        for(int i = 5; i <= n; ++i)  // 绳子有多长
        {
            for(int j = 1; j < i; ++j)  // 在长度i时,分两段,其中一段长度为j
            {
                dp[i] = max(dp[i], j*dp[i-j]);    // 在多次剪法中找到剪法使得乘积最大,而且发现这是一个增长数组
            }
            // std::cout << i << " " << dp[i] << std::endl;
        }
        return dp[dp.size()-1];
    }
};

挤挤刷刷! 文章被收录于专栏

记录coding过程

全部评论

相关推荐

05-30 18:54
武汉商学院 Java
湫湫湫不会java:先投着吧,大概率找不到实习,没实习的时候再加个项目,然后把个人评价和荣誉奖项删了,赶紧成为八股战神吧,没实习没学历,秋招机会估计不多,把握机会。或者说秋招时间去冲实习,春招冲offer,但是压力会比较大
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务