面试题14剪绳子动态规划

mxbday commented 4 years ago

int* products = new int[length + 1];
products[0] = 0;    
products[1] = 1;  // if (length < 2 )   return 0
products[2] = 2;
products[3] = 3;  // 这里和上面对不 f(3) = max(f(2)*f(1)) = 2

mxbday commented 4 years ago

想通了,这里是不剪的时候的值,建议在代码里面加个注释,不然很难理解

bigbearishappy commented 4 years ago

楼上的说法是有问题的，题目中明确要求剪为m段，并且m>1,说明至少需要剪一刀。因此不能理解为不剪的时候的值。关于这个数组值的含义，书本中描述的比较隐晦，需要结合代码来理解，书本中写道：“数组中第i个元素表示把长度为i的绳子剪成若干段后各段长度乘积的最大值。”，这里没有说明i范围，而结合前面的代码，我们才知道这里i的范围是i>=4。因此建议作者在这里加上范围说明，便于读者理解。那至于为什么products数组的前4个元素内容是书本中的那样，我认为这里需要用归纳法来进行推导：我们往后面计算几个数组的元素 products[4] = max(products[1]products[3], products[2]products[2]); products[5] = max(products[1]products[4], products[2]products[3]); 我们知道，正确情况下products[4]=4;products[5]=6; 而要得到这个正确结果，那么products的前4个元素只能是代码中所列的那样： products[0] = 0; products[1] = 1; products[2] = 2; products[3] = 3; 其实个人认为products[0]=0;这行代码没有存在的必要，它的存在反倒会给读者带来更多疑惑。

176ace1b140b3f commented 4 years ago

我也发现这个问题了，正确的解法更新在了

https://leetcode-cn.com/problems/jian-sheng-zi-lcof/solution/fa-xian-jian-zhi-offerdi-er-ban-zhong-ti-ji-de-don/

HannibalXZX commented 4 years ago

f(3) = 2 , products[3]=3 这里是因为，前面的3被切成了两段，所以最大值为2。后面这个3是当作一个因子，比如 6 = 23 。这样的话，f(6) = procucts(3]products[3]=9 , f(6) = f(3) * f(3) = 4 ,很明显后面答案是错的。

那范围为什么确定是>4呢？这里其实省去了一步，products[i] = max(f(i), i ) ，正好当i >3 时，恒能取products[i] = f(i) 所以就省略了

我认为这里还是要说明下

CoderQuinn commented 4 years ago

没问题，这些是在n>=4时，在至少已经剪过一次前提下的最优解； n<=3时，条件是要至少要剪一刀，然而不剪乘积是最大的

zhedahht / CodingInterviewChinese2

面试题14剪绳子动态规划 #74