题解 | #剪绳子#
剪绳子
https://www.nowcoder.com/practice/57d85990ba5b440ab888fc72b0751bf8
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int整型
* @return int整型
*/
public int cutRope (int n) {
if(n<5) {
return n;
}
// write code here
// f(n) = f(n-3) + 3
int[] dp = new int[n+1];
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
dp[4] = 4;
for(int i=5;i<=n;i++) {
dp[i] = dp[i-3]*3;
}
return dp[n];
}
}
由8推理可知需要尽可能多的3，那么容易得出动态规划的转移方程：f(n) = f(n-3) + 3
查看12道真题和解析