求一根棒可以切割的最大片数

Question

这是完整的问题陈述：

给定长度为 n 的绳子，您需要找到
可以制作的最大绳子数，使得对于
给定的三个值 a、b、c，每根绳子的长度都在集合 {a, b, c } 中

我知道可以通过动态规划来实现最优解，但是，我还没有学过这个主题，我需要递归地解决这个问题。对于递归，主要的事情是确定子问题，而这正是我主要遇到的困难。谁能给我一个直观的方式来思考这个问题？如果有意义的话，有点像递归的更高层次的描述。有没有与此类似的更简单的问题我可以先尝试来帮助我解决这个问题？

提前致谢。

Answer 1

这已经很简单了，通过递归我们可以检查所有可能性，一步我们可以从尺寸问题中切掉一段长度a, b, 或因此我们得到更小尺寸的超级问题cnn-x

当然，我们需要一个基本情况，所以当n=0我们成功时，我们可以返回0，如果n < 0我们失败，我们可以返回一些负无穷常数

示例伪代码：

int solve(int n){
    if(n < 0) return -123456789; //-Infinity
    if(n == 0) return 0;
    return 1 + max(solve(n-a), solve(n-b), solve(n-c));
}

进行动态规划就像设置备忘录查找表一样简单

int solve(int n){
    if(n < 0) return -123456789; //-Infinity
    if(n == 0) return 0;
    if(n in memo)return memo[n]
    return memo[n] = 1 + max(solve(n-a), solve(n-b), solve(n-c));
}