动态规划

1.从斐波纳契数列开始

//a.传统的递归实现

/*int fib(int n)             
{
  if(n==0 || n==1)
    return 1;
  else
   return fib(n-1)+fib(n-2); 

}*/

//b.保存每次已计算的数字

int fib(int n,map<int,int> fib_map)
{
  
  if(n==0 || n==1)
    return 1;
  else
  {
    map<int,int>::iterator iter = fib_map.find(n);
    if(iter==fib_map.end())
    {
      fib_map[n]=fib(n-1,fib_map)+fib(n-2,fib_map);
      return fib_map[n];
    }else
    
      return fib_map[n];
    
  }
}

 动态规划适用于一个问题可以利用  它的同一类型，规模变小+ 转移的状态  来求解

class Solution {  
public:  
    int lengthOfLIS(vector<int>& nums) {  
        int i, j, len = 1, SIZE = nums.size();  
  
    if(!nums.size())    //防止数组为空  
        return 0;  
  
    vector<int> D(SIZE, 1);  
  
    for(i = 1; i < SIZE; ++i)  
    {  
        for(j = 0; j <= i - 1; ++j)  
        {  
            if(nums[j] < nums[i] && D[j] + 1 > D[i]) //递增序列，若求非降子序列，改nums[j] <= nums[i]  
                D[i] = D[j] + 1;  
  
            if(len < D[i])  
            len = D[i];  
        }  
    }  
  
    return len;  
    }  
};  

求最长回文字符串

string longestPalindrome(string s) 
{
    int psize=s.size();
    int begin=0,maxlen=1;
    vector<vector<bool>> ispali(psize,vector<bool>(psize,false));
    for(int i=0;i<psize-1;i++)
    {
        ispali[i][i]=true;
        
        if(s[i+1]==s[i])
        {
          ispali[i][i+1]=true;
          begin=i;
          maxlen=2;
        }
    }
    ispali[psize-1][psize-1]=true;
    for(int len=3;len<=psize;len++)
    {
      for(int i=0;i<psize-2;i++)
      {
        int j=min((i+len-1),psize-1);
        if( (ispali[i+1][j-1]) && (s[i]==s[j]))
        {
           ispali[i][j]=true;
           begin=i;
           maxlen=j-i+1;
        }

      }
    }


return s.substr(begin, maxlen);     

}