中也有很多的人成为了相当出色的ACMer，当然了，这也是在他们付出了相当的努力之后才取得的结果。所以，我相信，只要你坚持下去，终会有收获的一天的。那么在下面一大点中，我想说下你们要攻克的几个最主要的方面。3动态规划Dy
amicProgrammi
g以下简称DP俗话说，要看一个人的算法水平，只要看一下他做DP题的水平就OK了，而在ACM这个多变的赛场上，几多算法沉浮，唯有DP几乎从未消失过，如果你问我什么类型的题在赛场上出现的概率最高，我可以毫不犹豫地告诉你，是DP。由此也可以看出，DP的地位有多么重要，那么这样一个几乎每场比赛都会出现的题型，应该很难啊，为什么要让我们从DP入手呢？确实，DP是很难，其变型之多，覆盖知识面之广，确实让人望而生却，但是，我想说下如何入门DP题。首先是DP几个最为基本的模型，LCS最长公共子序列，LIS最长上升子
序列，最大公共子段和，数塔问题，矩阵连乘等几个最为经典的问题，大家一开始的时候可能难以理解DP中自底向上，重叠子结构等基本思想，对于这几道问题可以先看一下别人的代码和书上的讲解，然后再自己反复地理解，理解了之后再自己敲一下代码，如果有地方实在
不理解，可以先放一下，去看看其他题，回过头来再想一下以前的题，也许会有豁然开朗的效果。吃透了DP的几个经典问题之后，就可以做一下这些经典问题的变型了，比如最大公共子段和的变型最大
f子矩阵和最大m子段和，最长公共子序列和最长上升子序列的变型最长公共上升子序列等等。并且可以尝试接触DP的一些重要的应用，最重要的要数背包问题，背包问题是DP一个很大的分支算是分支吧，我找不到其他更好的词来形容他了，同样也有非常多的变型，如最为基础的01背包，以及扩充出去的多重背包，完全背包，分组背
包，树型DP这个知识点我待会会介绍中应用非常多的泛化背包等等，下面我把最为基本01背包，多重背包和完全背包讲一下，首先是最简单的01背包，伪代码如下：fori1NforvV0fvmaxfvfvciwi这里为什么要倒推呢？其实道理很简单，因为这里其实是利用类似滚动数组的概念，只不过他连2个数组都不用开了，只需要开一个数组就可以了，这是为什么呢？因为传统的二维数组中fiv的值是由maxfi1vfi1vciwi得来的，所以每次fv的值是由上层循环中fvv’v得来的，所以改成了一维数组后，如果从小到大循环的话，在计算完成fv之后，就会在计算fvvv时发生错误，因为原r