【写在前面】《Java算法系列》目录如下（更新）：数据结构相关算法八种排序算法：冒泡排序、选择排序、插入排序、希腊语四种搜索算法：首尔排序、快速排序、归并排序、基数排序、堆排序：线性搜索、二分搜索、插值搜索、斐波那契搜索九种常用算法：分治算法、动态规划算法、KMP算法、贪心算法、Prim算法、Kruskal算法、Dijkstra算法、Floyd算法、KnightTravel回溯算法本文是动态规划算法中常用的九种算法。〇.基本介绍动态规划算法的核心思想是：将大问题分解成小问题求解，从而得到最优解逐步处理算法。动态规划算法类似于分而治之算法。它的基本思想是将待解决的问题分解成若干个子问题，先求解子问题，再从这些子问题的解中得到原问题的解。不同于分治法，它适用于动态规划求解的问题，分解得到的子问题往往不是相互独立的。对于下一个子阶段的解，动态规划算法是在上一个子阶段的解的基础上进一步求解。动态规划和贪心算法一样，是一种寻找最优解的思维方式。可以通过填表的方式逐步推进，得到最优解。为了方便做题，动态规划可以粗略地分为四类：线性动态规划、二维动态规划、树动态规划、背包问题。牛客网的动态规划项目将动态规划分为九大类：线性dp、前缀和、差分、二维dp、背包、区间dp、树dp、形压dp、数字dp。本文将介绍线性动态规划、二维动态规划、背包问题三大类。1线性动态规划1.1斐波那契数列问题需要输入一个正整数n，请输出斐波那契数列的第n项。本例参见：牛客网NC65斐波那契数列复习经典的“斐波那契数列问题”，斐波那契数可以定义两个初始条件和一个简单的递归公式：$$F(n)=\begin{cases}0,&n=0\\1,&n=1\\F(n-1)+F(n-2),&n>1\end{cases}$$除了用递归的方法求解，还可以用a非递归方法。F(n)的解可以计算出它的两个重叠较小的子问题F(n-1)和F(n-2)，所以n+1F(n)连续值：代码如下：publicclassSolution{publicintFibonacci(intn){如果(n<=1)返回n;int[]F=newint[n+1];F[0]=0;F[1]=1;for(inti=2;i<=n;i++){F[i]=F[i-1]+F[i-2];}返回F[n];}}动态规划算法可以解释为一种空间换时间的权衡技术。不过在“斐波那契数列问题”中，可以改进动态规划，避免使用额外的空间，这里不再赘述。1.2货币价值最大化问题给定一排n枚硬币，它们的面额都是正整数C1，C2，……，Cn，这些整数不一定成对不同。如何选择硬币，使得在它们的原始位置不相邻的情况下，所选硬币的总量最大。本例请参考：NC2非相邻取币如何选币？令F(n)为前n个硬币的最大可选数量。对于第n个硬币（n≥2），实际上有两种情况：如果第n个硬币没有被选中，则前n个硬币的最大可选数量与前n-1个硬币的最大可选数量一致，即：F(n)=F(n-1)选择第n个硬币，那么第n-1个硬币一定不能可选，前n个硬币的最大可选数量是第n个硬币加上前n-2个硬币：F(n)=Cn+F(n-2)这两种情况我应该选择哪种？两种情况都取最大值。因此，可以得到递推公式：$$F(n)=\begin{cases}0,&n=0\\C_1,&n=1\\max\{F(n-1),C_n+F(n-2)\},&n>1\end{cases}$$以一行硬币{5,1,2,10,6,2}为例，填表过程如下：最大前6个硬币的可选数量为，因此一行硬币{5,1,2,10,6,2}的最大可选数量为17。在构建一维表时，如果货币值数组是C[n]，那么动态规划数组应该是F[n+1]。硬币价值最大化问题的代码如下：publicclassSolution{//输入：数组C[0..n-1]保存n个硬币的面值publicintCoinRow(int[]C){intn=C.长度；如果(n==0)返回0；如果(n==1)返回C[0]；int[]F=newint[n+1];F[0]=0;F[1]=C[0];for(inti=2;i<=n;i++){F[i]=Math.max(F[i-1],C[i-1]+F[i-2]);}返回F[n];但是，上面的填表过程只是获取了最优解的值，并没有给出最优解。要找出最优解选择了哪些币种，还需要回到上面的计算过程。如何回溯？下面以“01背包问题”作为回溯过程的例子，思路是一样的。1.3非相邻访问问题牛客网动态规划题目的“非相邻访问问题”和币值最大化问题几乎一样：第一行输入一个正整数n，代表数组的长度。第二行输入n个正整数，代表整个数组。输出不相邻数的最大和。请参阅此示例：NC2非相邻访问。这是我的解决方案：importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);长n=sc.nextLong();long[]C=newlong[(int)n];for(inti=0;i
