转载：动态规划之公共串
动态规划（Dynamic programming，简称DP），是大家都觉得比较难以掌握的算法。为了应付面试，我们经常会背诵一下斐波那楔数列或者背包问题的源码，其实，只要理解了思想，掌握基本的模型，然后再来点写代码的套路，动态规划并没有那么难。
首先，动态规划最重要的是掌握他的思想，动态规划的核心思想是把原问题分解成子问题进行求解，也就是分治的思想。
1.线性模型
最经典的问题就是斐波那楔数列的问题，每个数的值都是一个状态，可以用F[i]表示表示第i个数的值是多少。每个数都是由F[i-1]+F[i-2]转移而来。
另外一个经典的问题就是最长上升自序列（LIS），有一串序列，要求找出它的一串子序列，这串子序列可以不连续，但必须满足它是严格的单调递増的且为最长的。把这个长度输出。示例：1 7 3 5 9 4 8 结果为4。
我们非常容易表示他的状态，我们用f[i]表示以第i个数结尾的，最大的上升自序列是多少？那么它是怎么转移的呢？非常容易想到肯定是从左边的的数转移而来，能转移的数满足什么条件呢？肯定是比a[i]更小的。
线性模式还可以拓展成二维问题，例如背包问题，用f[i][j]表示前i个物品，凑成大小为j的背包，最大的价值是多少。
这类问题非常的多，但是思路都是这样，无非就是从左往右，从上到下，从低维到高维进行转移。 2.区间模型 3.树状模型
1.爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ 注意：给定 n 是一个正整数。
class Solution { public int climbStairs(int n) { //1.特判 if(n < 3) return n; //2.边界 int[] dp = new int[n+1]; //楼梯：1-n dp[1] = 1; dp[2] = 2; //3.状态转移方程 for(int i = 3;i <= n;i++){ dp[i] = dp[i-1] + dp[i-2]; } return dp[n]; } }最长公共子串递推公式：（连续） 递推公式：
1 if(s1.charAt(i) == s2.charAr(j)) 2 dp[i][j] = dp[i-1][j-1] + 1; 3 else 4 dp[i][j] = 0; 1public static int maxLong(String str1, String str2) { 2 if (str1 == null || str2 == null || str1.length() == 0 || str2.length() == 0) 3 return 0; 4 int max = 0; 5 int[] dp = new int[str2.length() + 1]; 6 for (int i = 1; i <= str1.length(); i++) { 7 for (int j = str2.length(); j >= 1; j--) { 8 if (str1.charAt(i - 1) == str2.charAt(j - 1)) 9 dp[j] = dp[j - 1] + 1; 10 else 11 dp[j] = 0; 12 max = Math.max(max, dp[j]); 13 } 14 Util.printIntArrays(dp);//这一行和下面一行是打印测试数据的，也可以去掉 15 System.out.println(); 16 } 17 return max; 18}子序列：（不连续）
1 if(s1.charAt(i) == s2.charAr(j)) 2 dp[i][j] = dp[i-1][j-1] + 1; 3 else 4 dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);