两行代码解决:
剪绳子
http://www.nowcoder.com/questionTerminal/57d85990ba5b440ab888fc72b0751bf8
思路:如果能分的话,肯定是2和3越分越多越好,因为2和3是最小的素数,别的数字也都能由这两个数的任意倍数组合(例如4可以由两个2组成,5可以由一个2一个3组成,9可以由三个3组成)。
- 所以直接暴力递归代码如下,两行解决:
public class Solution { public int cutRope(int target) { if(target <= 3) return target; else return Math.max(2*cutRope(target-2), 3*cutRope(target-3)); } }
- 动规代码:
import java.util.*; public class Solution { public int cutRope(int target) { int[]dp = new int[target+1]; dp[2] = 2; dp[3] = 3; for(int i=4;i<=target;i++) //状态转移方程 dp[i] = Math.max(2*dp[i-2], 3*dp[i-3]); return dp[target]; } }