14- I. 剪绳子
动静布局：算法-动静布局 Dynamic Programming–从菜鸟到老鸟
求解的形式有两种：①自顶向下的备忘录法 ②自底向上。
一备忘录法也须要递归，因而个别用自底向上的办法，
思路一：动静布局，自底向上。
总体思路就是：从3的最大后果，计算到n的最大后果。
不来源gaodaima#com搞(代@码网同宰割形式用递归实现
i示意以后计算的绳子长度，j示意宰割的长度，i-j示意剩下的长度，每计算出一个后果都须要跟以后 i 对应的最大后果、宰割一次的后果、剩下长度的最优后果进行比照。即：
dp[i]、j*(i-j)、j*dp[i-j]
操作：
-
留神：
- 须要计算到n，因而数组到n+1
- j从2开始，因为割去1是有效的。
- 也可从4开始递归，然而运行工夫减少点点
思路二：贪婪(找法则)
单看7,8,9 - 3×4 除以3商：2 余：1 :3^(2-1)x4
- 3x3x2 除以3商：2 余：2 :3^2×2
-
3x3x3 除以3商：3 余：0 :3^3
操作：
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：关于java:14-I-剪绳子dp贪心找规律
转载请注明原文链接：关于java:14-I-剪绳子dp贪心找规律
