动态规划与部分枚举

枚举:

        在寻求最优解的时候,最简单的方法便是"枚举"。可别小看了枚举这简单的思路，凡是优秀、高效的程序大多有及其简单的原理。

                1、最大子序列和问题:

                        一串数字序列:1,-1,2,4,-3,6,8,求最大和的连续子序列。

                        枚举所有的子序列：起点为i,结束为j,稍作优化：时间复杂度为O(n^2);

                2、遥远的银河(问题源:la3695)

                        给出平面上n个点，找出一个矩阵，使得边界上包含尽量多的点。

                        枚举所有的矩形(需要压缩一下坐标)，左下角坐标为(i,j)，宽度和高度为w,h稍作优化，时间复杂度为O(n^4);

                3、最大子矩阵问题（题目源:la3029）

                        一个m*n的矩阵，其中一些格子是空地，其他的是障碍。找出一个全部由空地组成的面积最大的子矩阵。

                        枚举所有的子矩阵，左上角为(i,j)宽度和高度为w,h，稍作优化，时间复杂度为O(m*m*n*n);

部分枚举:

        1、最大子序列和问题:

                只枚举结束序列为j的最长子序列和,即可发现问题具有最优子结构特征:F(j+1) = max(F(j)，seq[j])，所以证明这样的部分枚举是可行的，时间复杂度为O(n)，稍作优化，空间复杂度为O(1);

        2、遥远的银河（问题源：la3695）

                部分枚举矩形的3边(而不是4边):左边x=l，右边x=r,上边y=i，可以发现问题具有最优子结构F(l,r,i+1)=max(C(i+i)+C(i)，C(i+1)+F(l,r,i)-B(i)))，其中C（i）表示从x=l,到x=r之间（包括边界上的点）在y=i上的点。B（i）表示不包括边界上的点。时间复杂度降为O(n^3)

                |                |

                |------------|  <i+1

                |------------|  < i

                |                |

                ^               ^

                l                r

        3、最大子矩阵问题（题目源:la3029）

                我曾做尝试这样部分枚举:枚举最右下角点为(i,j)的最大空地矩阵。但是这样做并没有发现子结构特征（但是倘若题目为求最大方阵，则可采用这样的枚举方案，参见数据结构stl一书）。

                在"算法竞赛入门经典-训练指南"一书中,作者给出的是不一样的枚举方式:枚举点(i,j)往上具有最高高度的最宽的矩形，如下图：$为空地，#为障碍

                ##$####

                ##$$###

                ##$$$##

                #$$$$$#

=========分隔符=================

                ##$####

                ##$$###

                ##$$$##

                #$$$$$#

=========分隔符=================

                ##$####

                ##$$###

                ##$$$##

                #$$$$$#

=========分隔符=================

                ##$####

                ##$$###

                ##$$$##

                #$$$$$#

最后

以上就是爱笑小鸭子为你收集整理的动态规划与部分枚举的全部内容，希望文章能够帮你解决动态规划与部分枚举所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。