ACM总结——动态规划（1）重叠子问题、最优子结构

动态规划(dynamic programming)简称DP。

先看几个简单的问题：

1，斐波那契数列

1,1,2,3,5,8......

求第n项

  

   

    

     

    
    

     

      int fac(int n)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    if(n<3)return 1;
     
    
   

    

     

    
    

     
    return fac(n-1)+fac(n-2);
     
    
   

    

     

    
    

     

      }
     
    
  
 

时间复杂度O (1.6 ^ n)

递归写法（备忘录法）：

  

   

    

     

    
    

     

      int ans[1000]={0};
     
    
   

    

     

    
    

     

      int fac(int n)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    if(n<3)return 1;
     
    
   

    

     

    
    

     
    if(ans[n])return ans[n];
     
    
   

    

     

    
    

     
    return ans[n]=fac(n-2)+fac(n-1);
     
    
   

    

     

    
    

     

      }
     
    
  
 

非递归写法：

  

   

    

     

    
    

     

      int ans[1000]={0,1,1};
     
    
   

    

     

    
    

     

      int fac(int n)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
    for(int i=3;i<=n;i++)ans[i]=ans[i-1]+ans[i-2];
     
    
   

    

     

    
    

     
    return ans[n];
     
    
   

    

     

    
    

     

      }
     
    
  
 

递归写法不需要控制DP的计算顺序，非递归写法需要严格控制计算顺序。

读者可此处思考一下上述递归写法的实际计算顺序，假设编译器是默认先执行加法左边的，再执行加法右边的。

两种写法的时间复杂度都是O（n）

为什么差异这么大？

这就是DP的第一个重要特性：重叠子问题

2，求数列中位数

这个题，能不能像上一题这么做呢？

如果我用f(n)表示数列前n个数的中位数，那么，由f(n-1)和f(n-2)可以直接推导出f(n)吗？

不能！

差异在哪？差异在于问题本身的性质不同。

这种由子问题的答案可以直接推导出原问题答案的性质，其实就是最优子结构。

最优子结构：问题的最优解包含了子问题的最优解。

再来看看一个动态规划的题目，当我们分析它的时候，我们在想些什么？

3，数列的DP问题

一维

力扣 OJ 300. 最长上升子序列

力扣OJ 1218. 最长定差子序列

二维

力扣 OJ 1143. 最长公共子序列

CSU - 1060 Nearest Sequence （三个数组的最长公共子序列）

4，最短路问题

动态规划的题目，当我们分析它的时候，主要就是：

问题研究的对象、问题的子问题、最优子结构（即递推式）、解空间结构

递归写法和非递归写法其实都是解空间的遍历，而绝大部分问题的解空间都可以映射为树空间，树的遍历主要就是DFS和BFS，递归基本上就是DFS。

什么是解空间结构？

解空间就是问题可能的解组成的集合，根据问题的属性，空间的结构也有不同，有的是数组有的是树等等。

按照问题研究的对象类型和解空间结构，DP问题可以分为数列DP、区间DP、树形DP、数位DP、状态压缩DP、概率与期望DP、高维DP等等。

DP的更深用法：

空间压缩、时间优化

文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nameofcsdn/article/details/106417240