从前面两个超级简单的例子我们能够总结出动态规划的核心就是找出状态转移方程。但是状态的定义我们需要仔细的琢磨琢磨，因为只有我们定义好状态是什么，我们才能够找到该状态的转移方程，有时候，我们会发现，状态定义之后，我们无法快速的得出转台之间的转移方程，此时就需要考虑是否应该换一个角度去思考状态。
我们依然从一个简单的例子开始
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 问总共有多少条不同的路径？ 说明：m 和 n 的值均不超过 100。 示例 1: 输入: m = 3, n = 2 输出: 3 解释: 从左上角开始，总共有 3 条路径可以到达右下角。 1. 向右 -> 向右 -> 向下 2. 向右 -> 向下 -> 向右 3. 向下 -> 向右 -> 向右 示例 2: 输入: m = 7, n = 3 输出: 28 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/unique-paths 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
首先读题，可以总结出两个有用的信息：
1、起始点和终止点被固定下来了。
2、机器人只能向下或者向右走，只有这两种情况。
根据以上的问题，我们开始思考，所谓的状态转移方程，其中的状态到底是什么状态。题目问的是路径，我们会很先入为主的想，状态就是路径，那么状态转移方程就会等价于路径转移方程，可是问题来了，给定一张图，路径也就是答案就是确定的了，不会存在任何的转移方程，路径转移也就没了意义。因此，我们需要注意，状态既然能够转移，那么这个东西肯定是能动的玩意儿，不能动还谈什么转移？很巧的是，本题直接给出了一个能动的玩意儿，这个就是机器人，但是需要明确，机器人作为一个物理实物是不变的，机器人不会变形金刚不会变成奥特曼，而是机器人的坐标会变，那么，由此，状态转移方程变成了坐标转移方程，此时，另一个巧合又出现了了。回到我们总结的两个有用信息。第二点恰好描述了坐标的运动状态。那么我们可以得到坐标转移方程
S[i-1][j] || S[i][j-1] -> S[i][j]
这个表达式翻译成人话就是，S[i][j]这个坐标，那么是机器人向下走到达的，要么是机器人向右走到达的。可是这和路径有啥关系？关系大了去了，既然两种方式走一步都能到达S[i][j]，也就是说，如果我们知道了s[i-1][j]或者s[i][j-1]的路径就能知道s[i][j]的路径，其等于
S[i][j] = S[i-1][j]+S[i][j-1];
那么此问题得解。
public int uniquePaths(int m, int n) { if(m==0 && n==0) return 0; if(m==1 || n==1) return 1; int[][] dp = new int[m][n]; for(int i=0;i<m;++i){ for(int j=0;j<n;++j){ if(i==0 && j==0) dp[i][j] = 1; if(i==0 || j ==0){ dp[i][j] = 1; } if(i>0 && j>0){ dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } } return dp[m-1][n-1]; }
上述代码实际上可以优化空间复杂度，感兴趣的可以试一下。
下面再看另一个超级简单的例子
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。 示例 1： 输入: "babad" 输出: "bab" 注意: "aba" 也是一个有效答案。 示例 2： 输入: "cbbd" 输出: "bb" 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-palindromic-substring 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
首先，依然是找状态，直接告诉我们，最长的回文串是没有状态的转移的。那么什么才是我们需要关注的状态呢？
没有思路时不要慌，按照通俗的做法，我们可以遍历字符串的所有子串，找到子串中所有的回文串，然后输出其中最长的回文串，我觉得这种算法虽然时间复杂度很高，但是不失为一种好办法，至少能解决问题嘛。我们不妨发散思维，在这种穷举的算法中，有一步关键的步骤，就是要找出所有的回文串。我们不妨大胆的想想如何去优化穷举算法，最容易想到的就是在找回文串处了，我们再不妨的假设，如果字符串S1是回文串，如何得到下一个回文串S2呢？
其实也很简单，在S1的两边添加一对一模一样的字符就好了。此时脑子突然灵光一闪，我们需要找啥玩意儿来着的？--状态，状态需要有什么特性？----状态至少能动，可以转移。此处不就是么，从S1转移到S2，然后长度增加了2，状态，转移，还和长度挂上钩了，感觉十分完美。不妨假设回文串就是我们的状态。
1、单个字符肯定妥妥的就是回文串嘛，左看右看都一样，
2、判断下一个状态是不是回文很简单，只需要判断它左边的字符和右边的字符是否相等。
经过上述两个步骤，我们可以很轻松的从一个回文串转移到另一个回文串，但是这个和题设有个毛的关系。仔细一想，在穷举中，不就是要找出子串中所有的回文串么？这么说，这几步和题设的问题还真有毛关系。
整理整理思路：
1、如果S1是回文，如果S2可以通过在S1两边添加上一组一样的字符构成，那么S2也是回文---------这是我们的状态转移方程，如果S1我们用str.sub(i,j)表示，即S1是str中以i为起始，j为结束的一个子串，S2=str.sub(i-1，j+1)，如果str.char(i-1) ==str.char(j+1)，则S2也是回文，若用dp矩阵标志S1和S2是否是回文，则dp[i][j]=true表示str.sub(i,j)是回文。
2、用一个变量len记录回文的长度，即len=j-i+1，条件是dp[i][j] = true;
3、用一个变量记录回文的起始位置，start，显然start和len是息息相关的，那么最长回文就是str.sub(start, start+len)
代码如下：
public String longestPalindrome(String s) { if(s.length()<2){ return s; }else { boolean[][] dp = new boolean[s.length()][s.length()]; //判断是不是回文串，dp[i][j]=true int maxLen = 1,start = 0; //因为一个字符就是回文，最大长度最小就是1 for(int i=0;i<s.length();i++){ dp[i][i] = true; //单个字符是回文 for(int j=0;j<i;++j){ //注意j在左边，i在右边，i>j if(s.charAt(i) == s.charAt(j) && (i-j==1||dp[j+1][i-1])){//两个字符相等时需要判断两个字符是否相邻(相邻没有中间，此时边界)或者中间字符串为回文，此时S2才是回文 dp[j][i] = true; if(i-j+1>maxLen){ //更新start和最大长度 maxLen = i-j+1; start = j; } }else dp[j][i] = false; } } return s.substring(start,start+maxLen); } }
小小的总结一下，当一眼看不出所谓的状态转移方程中的状态是个啥的时候，不要慌，穷举肯定能做出来，想办法优化穷举的过程中也许就可以灵光一闪呢？