剑指Offer——JZ67.剪绳子【DP | 贪心】

剑指Offer——JZ67.剪绳子【DP | 贪心】

​​题目传送门​​

题解

动态规划：

贪心：

其实很好发现：

AC-Code

DP：

class Solution {public: int cutRope(int number) { if(number < 2) return 0; if(number == 2) return 1; if(number == 3) return 2; int *dp = new int[number + 1]; memset(dp, 0, sizeof(dp)); dp[1] = 1; dp[2] = 2; dp[3] = 3; for(int i = 4; i <= number; ++i) for(int j = 1; j <= i / 2; ++j) dp[i] = max(dp[i], dp[i - j] * dp[j]); int ans = dp[number]; delete[] dp; return ans; }};

贪心：

class Solution {public: int cutRope(int number) { if(number < 2) return 0; if(number == 2) return 1; if(number == 3) return 2; return number % 3 == 1 ? pow(3 , (number/3 - 1)) * 4 : pow(3, (number / 3)) * 2; }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。