面试题 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;
}