什么是动态规划？
动态规划 （英语：Dynamic programming，简称 DP），是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题。（百度百科得到的答案）
简单的就是说：用简单的方法来解决复杂的问题！
核心思想：
动态规划的核心就是 有记忆，减少不必要的计算！
动态规划的做题方法
一般我们在做动态规划这种题的时候一般会有一下这几个步骤：
定义一个的dp数组。
dp数组的初始化。
列举动态规划推导公式。
进行循环遍历逐步改变dp数组的值，直道循环结束能获取我们所需要的值即可。
我们只要上述的几个步骤没有出现什么问题的话，那么这个这个题也就是手到擒拿了！
而上述步骤中比较难的就是 动态规划推导公式 的推导，一般在做题时我们很容易的知道这个题是用动态规划来解决这个问题。但是每次就会卡到动态规划推导公式这个地方（不要问我为什么5555）。所以这个也是我们需要提高的地方！！！
给大家一些 建议 ，在做动态规划题的时候 一定要自己推导自己的动态规划推导公式 ，就算写不出来我们在看题解的时候也可以那我们自己推导出来的公式和官方的公式进行一个对比，每次在做题的时候只要能保证这点，则以后的进步就会越来越大！！！
一维DP
简介
在上面我们已经知道了什么是 DP 了，那么什么又是 一维DP 呢？
一维DP：
通常的讲 一维DP 就是通过一维的数组来满足 推导公式 的一个求解。
int[] dp = new int[10];//则表示创建了一个长度为10的一维DP数组。 //例如：推导公式 dp[i] = max(dp[i - 2] + dp[i - 1] , dp[i])//这个就是一个比较简单的一维DP推导公式！
走进一维DP
上述中我们知道了什么是 一维DP ，那我们就要来走进这个它，并且征服它！同学们来看下面的例题吧。
例题：
509. 斐波那契数
题目：
斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1
示例：
输入：n = 2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1 1
做题步骤：
还记得我们第一步需要怎么来分析的吗？
第一步我们需要确定这题的 DP 数组该怎么去创建？
第二步需要我们推导出本题的 DP 公式。
第三步进行循环得到我们需要的结果。
思路：
通过做题步骤我们能知道这个 DP数组 的长度是 n + 1 （因为需要从0开始到n，所以长度也就是 n + 1 ）
题目所说从 1 后面开始每一项的数字都是前两项的和。通过解析这句话我们能知道我们的 循环是从2开始，到n结束 。而推导公式则就是：
dp[i] = dp[i - 1] + dp[i - 2]
当我们完成上述的步骤时接下来就是将这题给实现了。
代码：
Python版本：
class Solution: def fib(self, n: int) -> int: if n < 2: return n dp = [0]* (n + 1) dp[1] = 1 for i in range(2 , n + 1): dp[i] = dp[i - 1] + dp[i - 2] return dp[n]
Java版本：
class Solution { public int fib(int n) { if (n == 0) return 0; if (n == 1) return 1; int[] dp = new int[n + 1]; dp[1] = 1; for (int i = 2; i < n + 1; i++){ dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n]; } }
我们做了一个比较简单的DP题，那我们再来看另外一个简单的DP问题吧
题目：
746. 使用最小花费爬楼梯
给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。
示例：
输入：cost = [10,15,20] 输出：15 解释：你将从下标为 1 的台阶开始。 - 支付 15 ，向上爬两个台阶，到达楼梯顶部。 总花费为 15
做题步骤：
DP数组 的创建。
推导出本题的 DP 公式。
进行循环。
思路：
在题目的含义中我们已经知道了 用最小的花费来达到顶楼！ 则我们需要创建的 DP数组 长度就为 n + 1 (第n 个下标代表的是楼顶)。则也能得到动态规划的公式和循环的开始点和结束点！
动态规划公式：
dp[i] = min(dp[i-1]+cost[i-1],cost[i-2]+dp[i-2])//从4开始的循环公式 dp[i] = min(dp[i - 1] + cost[i - 1], cost[i - 2] )//当i是等于3的时候判断方程式 dp[i] = min(cost[i - 1], cost[i - 2])//等于2的时候的一个公式
代码：
Python版本
class Solution: def minCostClimbingStairs(self, cost: List[int]) -> int: dp = [0 for i in range(len(cost)+1)] for i in range(2,len(cost)+1): if i ==3 : dp[i] = min(dp[i - 1] + cost[i - 1], cost[i - 2] ) elif i ==2 : dp[i] = min(cost[i - 1], cost[i - 2]) else: dp[i] = min(dp[i-1]+cost[i-1],cost[i-2]+dp[i-2]) return dp[len(cost)]
Java版本：
class Solution { public int minCostClimbingStairs(int[] cost) { int[] dp = new int[cost.length + 1]; for(int i = 2; i < cost.length + 1; i ++){ if (i == 2){ dp[i] = Math.min(cost[i - 1], cost[i - 2]); } else if (i == 3){ dp [i] = Math.min(cost[i - 2] , dp[i - 1] + cost[i - 1]); }else{ dp[i] = Math.min(cost[i - 1] + dp[i - 1] , cost[i - 2] + dp[i - 2]); } } return dp[cost.length]; } }
OK，例题看完了，接下来就是来看习题了哦！！！
