动态规划对于笔者来说有很重要的意义

一、题目如下：

对于此类题目,笔者常用的的办法是先做个暴力解题思路,然后再对暴力法进行优化。

二、暴力法

//字串遍历public static String longestPalindrome(String s) {   String result="";    if(s.length()==1) return s;for(int i=0;i
     
      result.length())result=s.substring(i,j);}}return result;}//回文判断public static boolean test(String str) {
    for(int i=0;i
     

 

这段代码虽然不出意外的超时了，但是确实是我们第一步要考虑的。这个暴力法很简单，一个一个字串的检测，直到检测完所有的字符串。可是这不是我们想要的。

三、动态规划方法

首先要修改的就是我们的第一个字符串遍历的方法。思路为，既然我们知道了一个串为回文，那这个串左字母和右字母如果相同的话,不就又是一个回文字符串了吗。

不过这个思路要解决的问题有俩个：

1.找到所有起始字符串,并且将这些字符串下标保存到ArrayList数组里面

2.对每个字符串进行动态扩张。扩张到不能再扩为止。

public static String longestPalindrome(String s) {        //定义一个结构保存所有字串        class Str{            Str(int i,int j){                this.i=i;                this.j=j;            }            int i;            int j;        }        if(s.length()==1) return s;        ArrayList
     
       al =new ArrayList<>();        for(int i=0;i
      
       =(large.j-large.i)) large=str;        }        return s.substring(large.i,large.j+1);            }
      
     

 

四、笔者对动态规划法的看法。

动态规划没有确切的定义，但拿这题来说，笔者只是把所有需要的数据存储在内存中。再把这些数据拿出来进行动态扩张。