动态规划第三讲——序列化的动态规划问题

例一：最长上升子序列。

最长上升子序列问题，有一个正整数数列，长度n在1000之内，元素a[i]在10^5之内，求最长递增子序列的长度。

这里，时间复杂度是O(n^2);在递归与分治法过后，是不是发现了问题的端倪呢？到这里，我们就可以很方便地转化成动态规划的问题了。形式有两种，读者可以自己去实现：1）dp[i]:以a[i]开始的最长递增子序列的长度；2）dp[i] 以a[i]结尾的最长递增子序列的长度

Eg2：Word Break

class Solution {                
public:           
         bool wordBreak(string s, unordered_set<string> &dict) {
             int n=s.size();
             if(n==0) return true;
             bool dp[n+1];
             fill(dp, dp+n+1, false);
             dp[0]=true;
             int i, j;
                     
             for (i = 0; i < n; ++i){
                 for(j=i;j>=0;j--){
                    if(dp[j]){
                        if( dict.find(s.substr(j, i+1 - j)) != dict.end() ){
                            dp[i+1]=true;
                            break;
                        }   
                    }   
                 }   
             }   
             return dp[n];
         }   
};  

动态规划第三讲——序列化的动态规划问题

原文：http://blog.csdn.net/trochiluses/article/details/38017007