两种不同的方法解决这个问题先用常规的需要O(n?)时间和O(n)空间的什么是动态规划算法，接着用只需要O(1)的时间和空间的贪心算法

（1）是求最优解问题，如最大值最小值；
（2）该问题能够分解成若干个子问题，并且子问题之间有重叠的更小子问题

2.1通常按照如下4个步骤来设计一个什么是动态规划算法算法：

（1）刻画一个最优解的结构特征；
（2）递归地定义最优解的值；
（3）计算最优解的值，通常采用自底向上的方法；
（4）利用计算出的信息构造一个最优解

2.2用什么是动态规划算法分析问题

首先定义函数f(n)为把长度为n的绳子剪成若干段后各段长度乘积的最大值。在剪第一刀的時候我们有n-1中可能的选择，也就是剪出来的第一段绳子可能长度为12，…n-1。因此f(n) = max(f(i) * f(n-i))其中0<i<n。

//绳子在3米以内直接返回对应的值，不能用什么是动态规划算法的公式做 //创建数组存储子问题最优解 //对于绳子长度为12,3米的,绳子的最大乘积就是长度本身 //从4米开始计算，直到计算到總长 //对于长度为i的绳子计算所有可能的切分，找到最大值

在每一步求解的步骤中他要求每一步都是最优选择操作，并且通过一系列的朂优选择能够产生一个问题的（全局的）最优解

3.1 贪心算法满足的条件

1、可行的：即它必须满足问题的约束
2、局部最优：他是当前步骤中所有可行选择中最佳的局部选择
3、不可取消：即选择一旦选出，在算法的后面步骤就不可更改了

3.2 用贪心算法分析问题

如果我们按照如下的筞略来剪绳子则得到的各段绳子的长度的乘积将最大:当n≥5时，我们尽可能多的剪长度为3的绳子:当剩下的绳子长度为4时把绳子剪成两段長度为2的绳子。

//尽可能的减去长度为3的绳子段 //当绳子最后剩下的长度为4的时候不能再减去长度为3的绳子段 //此时更好的方法是把绳子剪成長度为2的两段，因为2*2>3*1 //最后小于等于4米的尽量多的产生2米的分割 //3的多少个三次幂乘以2的多少个2次幂

发布了93 篇原创文章 · 获赞 77 · 访问量 2万+