动态规划算法与分治法的思想类似，都是通过组合子问题的解来求原问题。我先来给大家介绍一下分治思想，分治思想就是把一个复杂的问题，分解为k个规模相同的子问题，如果还是无法解决，子问题又可以分为若干个相同规模的子问题求解，之后组合求原问题（难点）如二分法，归并排序，折半查找。至于动态规划：就是一个最优化问题，先将问题分解为子问题，并且对于这些分解的子问题自身就是最优的才能在这个基础上得出我们要解决的问题的最优方案（假设最优然后去求），要不然的话就能找到一个更优的解来替代这个解，得出新的最优自问题，这当然是和前提是矛盾的。同于 贪心算法，因为贪心算法是从局部最优来解决问题，而动态规划是全局最优的。用动态规划的时候不可能在子问题还没有得到最优解的情况下就做出决策，而是必须等待子问题得到了最优解之后才对当下的情况做出决策，所以往往动态规划都可以用 一个或多个递归式来描述。而贪心算法却是先做出一个决策，然后在去解决子问题。这就是贪心和动态规划的不同。

–摘自剑锋OI博文

题目出自SDUTOJ 题解： 我们要求最长上升子序列的长度，自然要挨个数字来寻找，这时我们用dp[i]来表示用i个数字结尾的最长上升子序列的长度。 样例 1 7 3 5 9 4 8 dp[i] 1 2 2 3 3 … dp[2]： dp[2]=dp[1]+1; dp[3]: dp[3]=dp[1]+1; dp[4]: dp[4]=dp[1]+1; dp[4]=dp[3]+1; 这时我们发现了什么规律呢？ 没错从第一位数字开始寻找，找到一个比当前的数小的数就+1更新一下，直到遍历到当前数字。 我们就得到状态转移方程 dp[i]=max( dp[j] + 1, dp[i] ) 0 n; dp[0]=0; a[0]=-1; //注意这里为什么要让a[0]=-1?还是说让a[0]小于某个数就行？ 继续往下看 for(int i=1;i>a[i]; for(int j=0;j