1 题目

剑指 Offer 14- I. 剪绳子

动态规划介绍：算法-动态规划-《算法导论3rd-P215》_hclbeloved的博客-CSDN博客

2 代码实现

class Solution {
public:
    int cuttingRope(int n) {
        vector<int> dp(n+3,1);
        dp[2] = 1, dp[3] = 2, dp[4] = 4;
		for (int i = 5; i <=n; ++i)
		{
			for (int j = 2; j <= i / 2; ++j)
			{
				dp[i] = std::max(dp[i], (j>dp[j] ? j : dp[j]) * ((i-j)>dp[i-j] ? (i-j) : dp[i-j]));
			}
		}

        return dp[n];
    }
};