题解 | #剪绳子#

#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];
    }
};