关于 Java 中的动态规划（Leetcode.53 最大子序和）

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.（Leetcode 53. Maximum Subarray）

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

输入: [-2,1,-3,4,-1,2,1,-5,4],输出: 6 说明: 连续子数组 [4,-1,2,1] 的和最大，为 6。

这是Leetcode上数组部分关于动态规划的一个简单的题目，动态规划只是他的一个基础解法，在这里记录关于动态规划的一些思路和想法。

什么是动态规划?

关于动态规划，维基百科是这样说的(看不懂)：

动态规划（英语：Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。

简单来说，就是大事化小，小事化了。也就是按照一定的规则方法，找到其中的一般规律，通过这种方法，减少计算量和时间复杂度。

怎么找规律？

对于动态规划类型的问题，找规律就是跟找递归规律是一个味道，总结来说，就是有和无的操作。

此话此话怎讲？以本题来说：我们从数组的最后一位来看 opt[8] (也就是最后一位），他的最大和可以是两种情况，一种是前一个数(包含前一个数在内的)的最大和，或者是自己本身。

Leetcode.53 最大子序和

在做分析的时候，从后往前看，出现结果最大的情况包含两种，一种是自己本身，另外一种是前一个数字的最大和加上自己本身。将其抽象化可以获得其的一般规律：

动态规划的相关问题

通过分析，解决的方法就被我们分析出来了，但观察上式，很容易会认为这个是一个递归的解法，其实，没得任何毛病，但认真想想，递归的执行其实跟我们分析的顺序是一样的，他在执行中会存在重复计算的问题：

斐波那契数列 就是一个很直观的栗子

在数学上，费波那契数列是以递归的方法来定义:

$f(n)={\begin{cases}0&\quad n = {\text{0}}\\1&\quad n = {\text{1}}\\f({\text{n-1}})+f({\text{n-2}})&\quad n≧2\end{cases}}$

当我们需要计算 $f(8)$ 的时候，就需要计算 $f(7)和f(6) 而 f(7) 又等于f(6)+f(5),f(6)$ 在这个地方就被重复计算了。

当我们计算某一个位的数字的值的时候，出现重复计算，将会导致最终的复杂都成几何倍增长。

Java 代码的实现

Java的一种实现

最后编辑于：2019.03.11 13:31:10