面试题 14- I. 剪绳子
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
static int cuttingBamboo(const int bamboo_len) {
vector<int> dp(bamboo_len+1,0); // dp数组存放乘积max
if(bamboo_len<=1) return 0; // 切割无效
for(int i=2;i<=bamboo_len;i++) // i表示绳子的长度
{
for(int j=1;j<i;j++) // 在长i的绳子的j处切割
{
dp[i]=max(dp[i], max(j*(i-j),j*dp[i-j]));
}
}
return dp[bamboo_len];
}
};
int main()
{
constexpr int bamboo_len = 10;
cout << "Maximum product for bamboo length " << bamboo_len << " is: " << Solution::cuttingBamboo(bamboo_len) << endl;
return 0;
}
标签:int,Day4,len,Offer68,bamboo,include
From: https://www.cnblogs.com/itsinsane/p/18516609