动态规划相信大家都知道，动态规划算法也是新手在刚接触算法设计时很苦恼的问题，有时候觉得难以理解，但是真正理解之后，就会觉得动态规划其实并没有想象中那么难。网上也有很多关于讲解动态规划的文章，大多都是叙述概念，讲解原理，让人觉得晦涩难懂，即使一时间看懂了，发现当自己做题的时候又会觉得无所适从。我觉得，理解算法最重要的还是在于练习，只有通过自己练习，才可以更快地提升。话不多说，接下来，下面我就通过一个例子来一步一步讲解动态规划是怎样使用的，只有知道怎样使用，才能更好地理解，而不是一味地对概念和原理进行反复琢磨
动态规划
算法思想理解动态规划
斐波那契数背包问题凑零钱问题 经典动态规划
最大连续和最长递增子序列
动态规划定义
动态规划是一个从统筹学借鉴过来的词语，常被用来优化递归
对动态规划（Dynamic programming）的理解
它的大概意思先将一件事情分成若干阶段，然后通过阶段之间的转移达到目标。由于转移的方向通常是多个，因此这个时候就需要决策选择具体哪一个转移方向，因此
阶段之间可以进行转移，这叫做动态达到一个可行解(目标阶段) 需要不断地转移，那如何转移才能达到最优解？这叫规划 算法思想
动态规划问题的一般形式就是求最 值,常用来优化递归算法。比如说让你求最长递增子序列呀，最小编辑距离呀等等。
既然是要求最值，核心问题是什么呢？求解动态规划的核心问题是穷举。因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值呗。
这么一说，好像动态规划很简单？
但是，动态规划的穷举有点特别，因为这类问题存在「重叠子问题」，如果暴力穷举的话效率会极其低下，所以需要「备忘录」或者「DP table」来优化穷举过程，避免不必要的计算。
而且，动态规划问题一定会具备「最优子结构」，才能通过子问题的最值得到原问题的最值。
另外，虽然动态规划的核心思想就是穷举求最值，但是问题可以千变万化，穷举所有可行解其实并不是一件容易的事，只有列出正确的**「状态转移方程」**才能正确地穷举。
以上提到的重叠子问题、最优子结构、状态转移方程就是动态规划三要素
理解这些名词最好的方法就是在题目中去感受它们，刷题越多，对动态规划也就有了一定的感觉
理解动态规划 斐波那契数它并不是动态规划问题，但是可以帮助理解 重叠子问题 这个概念
题目：求斐波那契数
斐波那契数列指的是这样一个数列：1，1，2，3，5，8，13，21，34，55，89…
这个数列从第3项开始，每一项都等于前两项之和
重叠子问题：用来求解原问题的递归算法反复地解同样的子问题，而不是总是在产生新的子问题。对两个子问题来说，如果它们确实是相同的子问题，只是作为不同问题的子问题出现的话，则它们是重叠的
public static int fibonacci(int n){
if (n== 1||n==2)
return 1;
return fibonacci(n-1)+fibonacci(n-2);
}
画出递归树，可以看到如果要求 fibonacci(20), 那么fabnacci(18)会涉及到重复计算，存在大量重复计算，比如fabnacci(18)被计算了两次，而且你可以看到，以fabnacci(18)为根的这个递归树体量巨大，多算一遍，会耗费巨大的时间。更何况，还不止fabnacci(18)这一个节点被重复计算，所以这个算法及其低效。
明确了问题，其实就已经把问题解决了一半。即然耗时的原因是重复计算，那么我们可以造一个「备忘录」，每次算出某个子问题的答案后别急着返回，先记到「备忘录」里再返回；每次遇到一个子问题先去「备忘录」里查一查，如果发现之前已经解决过这个问题了，直接把答案拿出来用，不要再耗时去计算了
演进一：带备忘录的递归解法
//带备忘录的递归
//时间复杂度O(n)
public static int fib(int n){
int[] memory = new int[n+1];
return fib(n,memory);
}
public static int fib(int n,int[] memoary) {
//base case
if (n == 1 || n == 2) return 1;
if (memoary[n]!=0) return memoary[n];
memoary[n] = fib(n-1,memoary)+fib(n-2,memoary);
return memoary[n];
}
本算法不存在冗余计算，子问题就是fib(1),fib(2),fib(3)…fib(20)，数量和输入规模 n = 20 成正比，所以子问题个数为 O(n)。
至此，带备忘录的递归解法的效率已经和迭代的动态规划一样了。实际上，这种解法和迭代的动态规划思想已经差不多，只不过这种方法叫做「自顶向下」，动态规划叫做「自底向上」。
优化二：dp 数组的迭代解法–引出状态转移方程
有了上一步「备忘录」的启发，我们可以把这个「备忘录」独立出来成为一张表，就叫做 DP table 吧，在这张表上完成「自底向上」的推算
//时间复杂度O(n)
public static int fib2(int n) {
int[] dp = new int[n + 1];//DP table
dp[1] = dp[2] = 1;//base case
for (int i = 3; i <= n; i++)
dp[i] = dp[i - 1] + dp[i - 2];//状态转移方程
return dp[n];
在这里引出「状态转移方程」这个名词，实际上就是描述问题结构的数学形式
我把它理解为一个分段函数，例如对斐波那契数这个例子
希望读者可以通过这个例子对重叠子问题和状态转移方程有一个基本的理解，但是动态规划的另一个重要特性「最优子结构」，并没有在这个例子中涉及到，因为斐波那契数列的例子严格来说不算动态规划，因为没有涉及求最值，以上旨在演示算法设计螺旋上升的过程。
我们来看下一个问题
背包问题01背包：每种物品不可重复完全背包：每种物品可以无限使用
凑零钱问题0—1背包
给你一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性。其中第i个物品的重量为wt[i]，价值为val[i]，现在让你用这个背包装物品，最多能装的价值是多少
力扣322. 零钱兑换
题目：给你k种面值的硬币，面值分别为c1, c2 ... ck，每种硬币的数量无限，再给一个总金额amount，问你最少需要几枚硬币凑出这个金额，如果不可能凑出，算法返回 -1 。算法的函数签名如下：
// coins 中是可选硬币面值，amount 是目标金额 int coinChange(int[] coins, int amount);
通过这道题理解最优子结构这个概念为什么说它符合最优子结构呢？比如你想求amount = 11时的最少硬币数（原问题），如果你知道凑出amount = 10的最少硬币数（子问题），你只需要把子问题的答案加一（再选一枚面值为 1 的硬币）就是原问题的答案
既然确定了这是一个动规问题，给出一个动规问题考虑的框架
明确「状态」 -> 定义 dp 数组/函数的含义 -> 明确「选择」-> 明确 base case。
我们回到凑零钱问题
找到变化的状态： 目标金额amount
确定dp函数的定义：函数 dp(n)表示，当前的目标金额是n，至少需要dp(n)个硬币凑出该金额
确定「选择」并择优： 也就是对于每个状态，可以做出什么选择改变当前状态。
具体到这个问题，无论当的目标金额是多少，选择就是从面额列表coins中选择一个硬币，然后目标金额就会减少、
自底向上使用 dp table 来消除重叠子问题，dp[i]表示，当目标金额为i时至少需要i枚硬币
public int coinChange(int[] coins, int amount) {
int max = amount + 1;
//定义dp数组大小为amount+1,初始值也为amount+1,
//为什么dp数组初始化为amount + 1呢，因为凑成amount金额的硬币数最多只可能等于amount（全用 1 元面值的硬币），所以初始化为amount + 1就相当于初始化为正无穷，便于后续取最小值
int[] dp = new int[amount + 1];
Arrays.fill(dp, max);
dp[0] = 0;//base case
for (int i = 1; i <= amount; i++) {//amount为金额
for (int j = 0; j < coins.length; j++) {
if (coins[j] <= i) {//如果可以用硬币表示
//找到上一个数+x个硬币数量的最小值
dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
}
}
}
//所需要金币数量大于金额，说明无解，返回-1
return dp[amount] > amount ? -1 : dp[amount];
}
经典动态规划
最大连续和求最大连续和问题
剑指 Offer 42. 连续子数组的最大和
问题描述
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
思路：可以用前缀和来做，这里我们说动态规划
难点在于对状态转移方程的定义：
用 dp[i] 代表以第 i 个数结尾的「连续子数组的最大和」
动态规划— 最佳实践 时间复杂度 O(n)
设滚动变量 dp ，代表以元素 nums[i] 为结尾的连续子数组最大和
class Solution {
public int maxSubArray(int[] nums) {
int pre = 0;
int dp = nums[0];//滚动变量
for (int x : nums) {
pre = Math.max(x + pre, x);
dp = Math.max(dp, pre);
}
return dp;
}
}
最长递增子序列
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
思路：
利用Hash表，key存储num[i],value存储num[i]对应的右边界
初始化哈希表，key和value都等于num[i]
遍历Hash表，动态更新每个数的最右边界，动态更新最大最右边界
//key存值，value保存右边界
public int longestConsecutive(int[] nums) {
HashMap map = new HashMap<>();
int ans = 0;
for (int num : nums)
map.put(num, num);//初始化
//更新边界
for (int num : nums) {
if (!map.containsKey(num - 1)) {//如果不包含上一个值，那么开始更新这个值
int right = map.get(num);
while (map.containsKey(right + 1)) {
right = map.get(right + 1);
}
//更新边界
map.put(num, right);
ans = Math.max(ans, right - num + 1);
}
}
return ans;
}
}
