题解 | #剪绳子#
剪绳子
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过程