Category Archives: 算法

动态规划算法的难点

1.容易陷入思维的定式,因为教科书在教授这段的时候,为了学生便于理解,设置了1,2,3,4…步骤去实现动态规划,比如上来第一条动态规划一般是为了解决最优化的问题,其实由局部解递推解决全局问题是一个很通用的设计方法,比如下面这个题目,
已知一个字符串,存在着很多的划分方式,现在我们要找一种划分,满足,
1. 每个子串都是回文串
2. 子串的个数最少

看到这些字眼,字符串,子串,最优解,似乎这是动态规划相当擅长的领域,
第一次尝试,我们引入f(str,i) 表示子串str[i…end]的满足条件的个数,那么f(str,0)就得到了最终的解,
那么怎么从 f(str,i) 推导出 f(str,i-1) 呢?一个直觉解是str[i]本身作为一个回文,那么f(str,i-1)=1+f(str,i),但这个解很可能不是最优的,很简单的一个反例\”aba\”,按照这种算法,算出来是 3,正确的结果是 1 。
第二次尝试,我们正向考虑问题,从 i 开始的子串,首先我们肯定知道这个值的最大值是这个子串的长度,而且很容易知道f(str,length(str)-1)=1 因为每一个单个字符都是一个回文,我们需要遍历检查所有的子问题,str[i…j]|j=i+1,i+2,i+3,如果str[i…j]是一个回文,那么用下面公式去重算最小值f(str,i)=min(1+f(str,j+1),f(str,i)),如果str[i…j]不是一个回文,那么用下面公式去重算最小值f(str,i)=min(1+j-i+f(str,j+1),f(str,i))

2.递归公式对于比较难的问题比较难写对,比如两个鸡蛋楼层问题,用两个鸡蛋去测试一个100层楼,在某一层的时候,鸡蛋掉下去会碎,现在为了找到这个临界层,并且在最坏情况下测试的次数最少,应该怎么选择测试方案?
不管3721,我们先写下了 f(m,n) 表示用m个鸡蛋测试n层楼最坏情况下的最少测试次数,接下来如何去缩小问题的规模?这一步不是特别直接,这个时候我们可以从问题本身来思考,我们必然要先选一个鸡蛋,然后选个楼层i扔下来,如果碎了,问题的规模变小,变成求1+f(m-1,i-1)。问题在于如果没碎的话,这个鸡蛋要从i层提高到哪一层呢?曾经在这里陷了很久,试图去找到这个楼层,但其实因为在这一层是没碎的,所以从i层以下扔都是不会碎的,我们完全可以假设在i层多了个地面,求解1+f(m,n-i) 是和原来的问题完全等价的,于是 f(m,n)=min{1+max(f(m-1,i-1),f(m,n-i))|i=0,1..n},这个等价就是求解的关键,但是多数人在这一步是没办法找到这个这个关系的,陷入了更复杂的思考 ——

“ 假设有 10 层楼,如果我先在 3 层往下扔没有碎,为什么问题就可以变成去检测 7 (10-3) 层楼的的问题呢??”

这个问题,我自己其实也没想清楚,所以动态规划的问题最终还是归结到
1. 一个问题的解是不是容易分解到子问题
2. 是不是子问题的解可以推导出原问题的解