上一篇博客写了分治解法以及为什么要用分治.
分治通过我们对子问题的定义, 实例化了我们每一步计算的语义, 从而帮助我们找到解空间中的重复结构.
在进行分治时, 我们找到了分割问题, 并用子问题的解表示问题解的方式, 也就是状态转移方程:
整个分治的计算过程分为两个阶段, 向下分割问题, 向上汇聚子问题的解从而得到问题的最终解.
再缓存中, 我们是从最小规模问题的解一步一步向上回归汇总成了大问题的解.
其实有了状态转移方程, 我们完全可以省略分割问题的步骤, 直接由小问题的解递推求的问题的最终解.
比如上述的状态转移方程, i 递增 / j 递减时是在分割问题, 那么我们直接从最小规模的子问题: i 最大, j 最小的情况开始, 按 i 递减 / j 递增 的顺序填充缓存即可递推的求出原问题的解.
填充的过程中需要注意处理边界情况, 在上述状态转移方程中边界情况有两类:
1. i 要小于字符串长度, 否则 i+1 会越界.
2. j 要大于 0 , 否则 j-1 会越界.
3. j 要大于等于 i , 因为 j 的语义是右边界, i 的语义是左边界.
因为 3 并且 i>=0, 所以 保证 3 便是 保证了 2, 我们只需要考虑 1,3 两种边界情况即可.
做一些题后有点感悟, 不管是分治也好动态规划也好, 解空间就摆在那里不会改变, 提高效率的是我们通过找到解空间的重复结构避免了重复计算. 基于我们对问题结构的定义. 对问题结构定义的越合理, 我们可以找出的解空间中可重复利用的部分就越多.
而贪心与回溯只是一种解空间的搜索手法, 在遇到特定场景时我们必须有这种思路, 它们在特定场景下是必须的, 而不是用来提高效率的.
剪枝则是避免无效计算, 直接的缩小了解空间的范围. 基于我们对问题本身的定义.
- int maxLength = 0;
- String ans = "";
- public final String dp(String source) {
- if (source == null || source.length() == 0) {
- return "";
- }
- int length = source.length();
- int[][] cache=new int[length][length];
- for(int left=length-1;left>=0;left--){
- for(int right=left;right<length;right++){
- // 边界处理
- if(left==right){
- cache[left][right]=1;
- continue;
- }
- if(left==length-1){
- if(cache[left][right-1]==1&&source.charAt(left)==source.charAt(right)){
- cache[left][right]=1;
- int tempLength=right-left;
- if(tempLength>maxLength){
- maxLength=tempLength;
- ans=source.substring(left,right+1);
- }
- continue;
- }
- cache[left][right]=-1;
- }
- // 子串否定, 主串直接否定
- if(cache[left+1][right-1]==-1){
- cache[left][right]=-1;
- continue;
- }
- // 子串为回文串, 判断主串
- char leftChar=source.charAt(left);
- char rightChar=source.charAt(right);
- if(leftChar!=rightChar){
- cache[left][right]=-1;
- continue;
- }
- // 主串也是回文串, 更新结果
- int tempLength=right-left;
- if(tempLength>maxLength){
- maxLength=tempLength;
- ans=source.substring(left,right+1);
- }
- cache[left][right]=1;
- }
- }
- if(maxLength==0){
- return source.substring(0,1);
- }
- return ans;
- }
来源: http://www.bubuko.com/infodetail-3458938.html