Comments (5)
想通了,这里是不剪的时候的值,建议在代码里面加个注释,不然很难理解
from codinginterviewchinese2.
楼上的说法是有问题的,题目中明确要求剪为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;这行代码没有存在的必要,它的存在反倒会给读者带来更多疑惑。
from codinginterviewchinese2.
我也发现这个问题了,正确的解法更新在了
from codinginterviewchinese2.
f(3) = 2 , products[3]=3
这里是因为,前面的3被切成了两段,所以最大值为2。后面这个3是当作一个因子,比如 6 = 2*3 。这样的话,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) 所以就省略了
我认为这里还是要说明下
from codinginterviewchinese2.
没问题,这些是在n>=4时,在至少已经剪过一次前提下的最优解;
n<=3时,条件是要至少要剪一刀,然而不剪乘积是最大的
from codinginterviewchinese2.
Related Issues (20)
- 面试题60 第二种解法是不是有问题啊,会int溢出
- Partition function has extremely bad performance for array with identical values
- 面试题三2 题解有问题 HOT 4
- #面试题37
- 面试题30 是否有必要总是将min(value, m_min.top())压入辅助栈中? HOT 1
- 面试68题答案错误
- 面试题17的本题扩展
- c
- 面试题54:二叉搜索树的第K大节点 HOT 1
- 第二版勘误
- Singleton
- 面试题19的题目有误? HOT 1
- 面试题3 题目二部分测试用例过不了 HOT 3
- pro
- 面试题10:斐波那契数列测试用例过不去 HOT 1
- 51题,数组中的逆序对
- List.cpp 头文件 #include "list.h" 有误
- How to build and run CommonParentInTree.cpp on macOS?
- Hu
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from codinginterviewchinese2.