很多人觉得动态规划很难,但它就是固定套路而已。其实动态规划只不过是将多余的步骤,提前放到dp数组中(就是一个数组,只不过大家都叫它dp),达到空间换时间的效果。它仅仅只是一种优化思路,因此它目前的境地和线性代数一样----虚假的难。
想想线性代数,在国外留学的学生大多数不觉得线性代数难理解。但是中国的学生学习线性代数时,完全摸不着头脑,一上来就是行列式和矩阵,根本不知道这玩意是干嘛的。 线性代数从根本上是在空间上研究向量,抽象上研究线性关系的学科。人家国外的教科书都是第一讲就帮助大家理解研究向量和线性关系。 反观国内的教材,直接把行列式搞到第一章。搞的国内的学生在学习线性代数的时候,只会觉得一知半解,觉得麻烦,完全不知道这玩意学来干什么。当苦尽甘来终于理解线性代数时干什么的时候,发现人家国外的教材第一节就把这玩意讲清楚了。你只会大骂我们国内这些教材,什么狗东西(以上是自己学完线性代数后的吐槽,我们同学无一例外都这么觉得)。
而我想告诉你,动态规划和线性代数一样,我学完了才知道,它不过就是研究空间换时间,提前将固定的重复操作规划到dp数组中,而不用暴力求解,从而让效率极大提升。
但是网上教动态规划的兄弟们,你直接给一个动态方程是怎么回事?和线性代数,一上来就教行列式和矩阵一样,纯属恶心人。我差不多做了30多道动态规划题目,才理解,动态方程只是一个步骤而已,而这已经浪费我很长时间了,我每道题都一知半解不理解,过程及其痛苦。最后只能重新做。 动态规划,一定是优先考虑重复操作与dp数组之间的关系,搞清楚后,再提出动态方程。而你们前面步骤省略了不讲,一上来给个方程,不是纯属扯淡吗? 我推荐研究动态规划题目,按5个步骤,从上到下依次来分析
DP数组及下标含义 递推公式 dp数组初始化 数组遍历顺序(双重循环及以上时,才考虑) dp数组打印,分析思路是否正确(相当于做完题,检查一下)
方法一:时间复杂度O(
n
2
n^2
n 2 ),空间复杂度O(n)
这种解法的思路,就是用dp数组保存小于等于目标值n的,每一个正整数值i,将i依次看做要拆分的数,找出它们每一个的最大乘积情况。最终递推到目标值n. 上面解析过程中,频繁出现i = j+(i-j) 和 i = j+dp[i-j]。这个初学者会很难理解。
i是我们当前要拆分的数,j是我们这次拆分必须有的数,比如i=10代表我们要拆分10这个数,试图找到它的最大乘积。而我们先从j=1开始枚举,也就是这次拆分,必须拆出一个1,剩下的你随便。再比如j=3时,就是我们这次必须先拆出来一个3,剩下的7你随便怎么拆。 而如果我们只想拆成2个数,比如10 = 1 + 9. i = 10. 而j = 1就表示我们这次拆出来的两个数里面,其中一个必须是1. 剩下一个数是多少呢?不就是10-1 ==> i-j = 9吗。这就有了10 = 1+(10-1) ==> i = j+(i-j) 那如果我们想拆成3和数或者更多呢?比如我们i = 10. j = 1,也就是这次必须拆出一个1. 那么剩下的9 我们随便怎么拆都行。拆成5和4,或者2和7,满足条件就行. 但是题目要求我们要最大情况。也就是说剩下的9,我们必须拆成最大的情况。 那么dp[9]表示的是什么呢?不就是将9拆分,然后乘起来后的最大情况吗?那么既然i = 10,j = 1,剩下的9我们又要拆分成最大情况。那么直接取dp[10-1] 不就可以了吗。 也就有了i = j+dp[i-j];
因此,这个解法的关键就是,算出从正整数1~n的每个数拆分后乘积的最大情况,保存到dp[i]中。
如何拆分:枚举每一种情况,用j表示这次拆分,必须拆出来的一个数。j从1开始一直枚举。显然这里是个可以优化的点。方法二会指出。 每种情况拆分后:算出乘积后,保留最大值,因为题目要求保留最大情况。
暴力求解的思想,就是从1到n一直尝试每一种值,每一种情况。 但是如果我们预先将其存储到dp数组,就可以直接通过dp, 获取数据,而不用枚举。典型的动态规划题目
暴力求解,需要每次对两个东西枚举,这种解法只需对一个东西枚举。第二种方法,不需要枚举。
DP数组及下标含义
我们要求出的是
当前数拆分后的数乘起来的最大情况。显然dp数组中存储的
就是当前数拆分后的数乘起来的最大情况。要求出谁的
?显然是对哪个数拆分。那么下标就是代表对哪个数拆分
,很显然,只需要一个下标,也就是一维数组。
递推公式
因为一个数最少拆成两个数,所以0和1没法拆成两个正整数,正整数从1开始。故:F(0) = F(1) = 0; 对于其它数i,都有两种情况,将当前数拆分成两个数,设其中一个数为j,则另一个数是i-j,也就是F(i) = j+(i-j) 另一种情况就是拆成3个及以上个数。设其中一个为j,则剩下的数是i - j = x。这个x拆分后乘积最大情况,我们已经规划过了,就是F(x). 故:F(i) = j+F(i-j)
dp数组初始化
数组遍历顺序(单重循环,无需考虑遍历顺序,一共就一维,哪里来的谁先谁后) 打印dp数组(自己生成dp数组后,将dp数组输出看看,是否和自己预想的一样。)
class Solution {
public int integerBreak ( int n) {
int dp[ ] = new int [ n+ 1 ] ;
for ( int i = 2 ; i <= n ; i++ ) {
int curMax = 0 ;
for ( int j = 1 ; j< i; j++ ) {
curMax = Math . max ( curMax, Math . max ( j* ( i- j) , j* dp[ i- j] ) ) ;
}
dp[ i] = curMax;
}
return dp[ n] ;
}
}
方法一优化:时间复杂度O(n*
l
o
g
2
n
log_2{n}
l o g 2 ? n )空间复杂度O(n)
我们每次拆分发现,最大情况下,拆出来的值,都相似,相差不多。而且它们都没有超过一半。比如n = 10 拆出的最大情况是4,3,3. 完全超不过它的一半,也就是超不过5 因此,我们枚举j的时候,只需枚举i/2次
class Solution {
public int integerBreak ( int n) {
int dp[ ] = new int [ n+ 1 ] ;
for ( int i = 2 ; i <= n ; i++ ) {
int curMax = 0 ;
for ( int j = 1 ; j<= i/ 2 ; j++ ) {
curMax = Math . max ( curMax, Math . max ( j* ( i- j) , j* dp[ i- j] ) ) ;
}
dp[ i] = curMax;
}
return dp[ n] ;
}
}
方法二:时间复杂度O(n),空间复杂度O(n)
通过数学归纳我们发现,例如10 = 3+4+3,拆分出的数字一个是它们都不会超过10的一半5.另一个它们都与10的一半5,相差2或者3. 也就是必然拆出2和3中的一个。这是大学数学相关课程的内容。如果你还对高数有印象,应该记得函数的极值如何求吧,但这是方法三会用到的。我们这里只是用了数学归纳法。
同样我们发现,2和3很固定,拆分2后结果为1,拆分3后结果为2.都是自己本身-1,也就是n-1. 所以如果题目要求我们拆分的n = 2或者3,直接返回n-1即可。
class Solution {
public int integerBreak ( int n) {
if ( n <= 3 ) {
return n - 1 ;
}
int [ ] dp = new int [ n + 1 ] ;
dp[ 2 ] = 1 ;
for ( int i = 3 ; i <= n; i++ ) {
dp[ i] = Math . max ( Math . max ( 2 * ( i - 2 ) , 2 * dp[ i - 2 ] ) , Math . max ( 3 * ( i - 3 ) , 3 * dp[ i - 3 ] ) ) ;
}
return dp[ n] ;
}
}
方法三:时间复杂度O(1),空间复杂度O(1)
导师让我今天这篇文章必须发出来,他晚上给编程小组讲课要用,但是这个方法,我还没想好怎么讲清楚,反正他们参加比赛也用不到这种难度的方法,所以日后补充。
写了两版稿子,依然不知道如何能讲解的通俗易懂,比如下面的驻点,我试图解释清楚,但涉及到了导数的定义和证明,我需要一定时间思考,如何让没学过微积分的人也能看懂。所以下面我先给出用数学做这道题的所需公式和最终代码。学过微积分的都可以很轻松做出来,因为这严格意义来说,难度只是一道高考的导数压轴题,放到考研数学里面,可能放到选择题第一题都让人觉得是送分题。会的人可以直接参考一下,日后我会补充。
class Solution {
public int integerBreak ( int n) {
if ( n <= 3 ) return n - 1 ;
int a = n / 3 , b = n % 3 ;
if ( b == 0 ) return ( int ) Math . pow ( 3 , a) ;
if ( b == 1 ) return ( int ) Math . pow ( 3 , a - 1 ) * 4 ;
return ( int ) Math . pow ( 3 , a) * 2 ;
}
}