【蓝桥杯】带你走进动态规划的世界（一）

【蓝桥杯】带你走进动态规划的世界（一）

写在前面

由于蓝桥杯对DP问题的考察加大，那么DP问题也就成了我们备考蓝桥杯的重点内容。我打算分三次写完DP，第一篇呢是为了让小伙伴们初步理解DP思想，里面的例题是非常经典同时又是非常基础的。
蓝桥杯的比赛时间越来越近了，所以最近我会加快备考文章的更新，小伙伴们不要着急噢~考前一定会将常考的知识点更新完的。
好啦废话不多说，进入我们今天的DP学习吧~

文章目录

• 写在前面
• 一、入门——从记忆化搜索说起
• 二、开端——什么是DP思想
• 三、切入——DP的分析方法
• • One Method 动规五部曲
  • Another Method 从集合角度去分析DP问题
• 四、分析——DP三大模型
• • 1. 组合模型——01背包问题
  • • 滚动数组优化 空间复杂度 O ( V ) O(V) O(V)
  • 2. 路线模型——摘花生
  • 3. 线性模型——最长上升子序列
• 写在后面

一、入门——从记忆化搜索说起

在前面的文章中我们已经对动态规划做了铺垫，不知道小伙伴们还记不记得在讲解搜索算法时我也给大家讲了记忆化搜索，还说记忆化搜索是学习DP思想的基础。有些小伙伴没看过之前的文章，因此呢这篇文章还是要从记忆化搜索说起。

以斐波那契数列为例，它的第一项为1，第二项为1，从第三项开始，每一项的值都是前面两项的和。让我们求第n项的是多少。对于这个问题，我们从最开始的递归思想来看。

int fib(int n)
{if (n == 1 || n == 2) return 1;return fib(n - 1) + fib(n - 2);
}

这个递归的时间复杂度是O(2^n)，随着n的增大，呈指数级别增长。递归的时间复杂度之所以高，是因为它涉及了很多重复性计算。比如在计算fib(5)的时候，fib(5) = fib(4) + fib(3)。接下来计算fib(4)，fib(4) = fib(3) + fib(2)。fib(4)计算完后就会再计算fib(3)。然而我们之前在计算fib(4)的时候已经算出fib(3)了。fib(3)被重复计算了两次。当n很大的时候。重复计算的工作就越来越多。

为了避免重复计算，我们可以在计算的过程中将已经计算过的值保存下来，等到再一次遇到的时候就可以直接使用。开一个dp[]数组，dp[i]存储fib(i)的值。dp[i] = 0表示还没有计算过。

int dp[20];
int fib(int n)
{if (n == 1 || n == 2) return 1;if (dp[n]) return dp[n];//计算过，直接返回dp[n]return dp[n] = fib(n - 1) + fib (n - 2);
}

说一下比较官方的东西，将每个求解过的子问题的解记录下来，当下一次遇到同样的子问题时，就可以直接使用之前记录的结果，而不用重复计算。这就是记忆化搜索的精髓。

下面我画两张图来让小伙伴们看看递归和使用记忆化搜索优化后的递归的搜索过程。

使用记忆化搜索后的时间复杂度为O(n)，将指数级别的复杂度降到了线性级别。

在下面对DP的讲解中，小伙伴们也会同样看到，DP会记录重复问题的解，下次再碰到时就会直接使用之前记录的问题的解。

二、开端——什么是DP思想

说明：以下对DP思想的讲解比较官方，不想看的小伙伴可以直接跳到第三大内容，DP的分析方法。

DP思想也就是动态规划思想，Dynamic programming，简称DP。

我们以一个数塔问题为例，给大家讲解以下到底什么是DP，什么情况下可以用DP等一些主要的问题。

将一些数字排成数塔的形状，其中第一层有一个数字，第二层有两个数字，第n层有第n个数字。现在要从第一层走到第n层，每次只能走向下一层连接的两个数字中的一个，问最后将路径上的所有数字相加后得到的和最大是多少？

我们可以尝试用DFS来解决这个问题，dfs维护已经选择完第index层，选择的数字是(index,y)，已经选择的数字之和sum。当处理完最后一层时用一个变量ans来更新数字之和的最大值。由于每个数字都有两个分支，因此

• 当前已经选择完第index层，选择的数为(index, y)
• 当前已经选择完第index层，选择的数为(index, y + 1)

穷举所有可能的时间复杂度是 O ( 2 n ) O(2^n) O(2n)。

#include <iostream>
using namespace std;const int N = 10;
int f[N][N];
int ans;
int n;void dfs(int index, int y, int sum)
{if (index == n){ans = max(ans, sum);return;}dfs(index + 1, y, sum +<