深入理解动态规划(dp)--(提前要对dfs有了解)

前言：对于动态规划：该算法思维是在dfs基础上演化发展来的，所以我不想讲的是看到一个题怎样直接用动态规划来解决，而是说先用dfs搜索，一步步优化，这个过程叫做动态规划。（该文章教你怎样一步步的解决这类题）

目录

一、动态规划入门

二、跳台阶问题---来自AcWing 

1.用暴力搜索dfs来解

2.记忆化搜索实现

3.递推实现

二、大盗阿福---来自AcWing

1.用dfs暴力搜索

2.记忆化搜索

3.递推实现

四、数字三角形---来自洛谷

1.用暴力搜索dfs

2.用记忆化搜索

3.递推dp

---

一、动态规划入门

动态规划就是：给定一个问题，我们将它拆解为一个个子问题，直到子问题可以直接解决，然后把子问题的答案保存起来，以减少重复计算，再根据子问题答案反推，得出原问题的一种方法

动态规划入门思路：dfs暴力--->记忆化搜索--->递推DP

下面正式开始讲解，还是在题中带大家慢慢理解动态规划的思维

二、跳台阶问题---来自AcWing 

一个楼梯共有n级台阶，每次可以走一级或者两级，问从第0级台阶走到第n级台阶一共有多少种方案。

输入格式：

共一行，包含一个整数n

输出格式：

共一行，包含一个整数，表示方案数

数据范围：

1<=n<=15

输入样例：

5

输出样例：

8

1.用暴力搜索dfs来解

• 这个题大部分同学都应该见过，最初我们用递归来解决这道题，其实本质上也是dfs暴力搜索

#include<iostream>
#include<algorithm>
using namespace std;
int n;
int fib(int x)
{if (x == 1)return 1;else if (x == 2)return 2;else return fib(x - 1) + fib(x - 2);
}
int main(void)
{cin >> n;int res = fib(n);cout << res << endl;return 0;
}

这时我们会发现，当n=41时，时间就快到了1s，所以要想办法去优化代码

2.记忆化搜索实现

这里我拿n=5为例，来画一下搜索树，然后分析一下怎么优化

 

如果是用一个数组来存储一下的话，直接就省去了这棵大树的右分支，因为左分支中的3已经搜索过了，当以后遇到别的题或者n更大时这棵树的左右分支也会很大，所以省去的搜索也就更多。 

#include<iostream>
#include<algorithm>
using namespace std;
int arr[100];
int n;
int fib(int x)
{if(arr[x])return arr[x];int sum=0;if (x == 1) sum=1;else if (x == 2) sum=2;else sum=fib(x-1)+fib(x-2);arr[x]=sum;return sum;
}
int main(void)
{scanf("%d",&n);int res = fib(n);printf("%d\n",res);return 0;
}

 直接将900多毫秒优化到了2毫秒。

3.递推实现

递归的过程：“归”的过程才是产生答案的过程

                      “递”的过程是分解子问题的过程（把大问题分解为子问题）

“递”：自顶向下

“归”：自底向上

而我们自底向上一步步推出答案的过程-----就是递推

好，接下来就用递推的方式进行编程：

#include<iostream>
#include<algorithm>
using namespace std;
int F[100];
int n;
int main(void)
{scanf("%d",&n);F[1]=1,F[2]=2;for(int i=3;i<=n;i++){F[i]=F[i-2]+F[i-1];//这个递推公式也就是dfs的状态转移公式}printf("%d\n",F[n]);return 0;
}

总结： 

跳台阶这道题：我们就是这样做的：

最暴力的dfs--->记忆化搜索--->递推（dp）

记忆化搜索=暴力bfs+记录答案

递推的公式=dfs向下递归的公式

递推数组的初始值=递归的边界

二、大盗阿福---来自AcWing

阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。这条街上一共有 N 家店铺，每家店中都有一些现金。阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。
作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。
他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金?
输入格式:
输入的第一行是一个整数 T，表示一共有 T 组数据。接下来的每组数据，第一行是一个整数 N ，表示一共有 N 家店铺,第二行是 N 个被空格分开的正整数，表示每一家店铺中的现金数量每家店铺中的现金数量均不超过1000。
输出格式:

对于每组数据，输出一行

该行包含一个整数，表示阿福在不惊动警察的情况下可以得到的现金

范围：

1<=T<=50

1<=N<=1e5

输入样例：

2

3

1 8 2

4

10 7 6 14

输出样例：

8

24

1.用dfs暴力搜索

先画搜索树，这道题是选和不选问题

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int arr[N];
int n, t;
int res = 0;
int dfs(int x)//x表示当前正在考虑哪家店
{if (x > n)return 0;else return max(dfs(x + 1), dfs(x + 2) + arr[x]);
}
int main(void)
{cin >> t;while (t--){cin >> n;for (int i = 1; i <= n; i++)scanf_s("%d", &arr[i]);int res = dfs(1);}return 0;
}

 放到官网提交一下答案发现，时间超时，因为dfs的时间复杂度是2的n次方，超时是理所当然的事，还是要想办法优化

2.记忆化搜索

要想实现记忆化搜索的话，那么dfs的参数就需要尽可能的少，不应该把没有影响到边界的参数放进来

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int arr[N];
int mem[N];
int n, t;
int res = 0;
int dfs(int x)//x表示当前正在考虑哪家店
{if (mem[x])return mem[x];int sum = 0;if (x > n) sum = 0;else sum = max(dfs(x + 1), dfs(x + 2) + arr[x]);mem[x] = sum;return sum;
}
int main(void)
{cin >> t;while (t--){cin >> n;for (int i = 1; i <= n; i++)scanf_s("%d", &arr[i]);memset(mem, 0, sizeof mem);int res = dfs(1);}return 0;
}

跟跳台阶一样的套路，创建一个数组，存放数据。

3.递推实现

前面也说过了，递推的过程就是递归的“归”，由搜索树的最底层开始向上推，并且递推的公式就是向下递归的公式.

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int arr[N];
//int mem[N];
int f[N];
int n, t;
int res = 0;
#if 0
int dfs(int x)//x表示当前正在考虑哪家店
{if (mem[x])return mem[x];int sum = 0;if (x > n) sum = 0;else sum = max(dfs(x + 1), dfs(x + 2) + arr[x]);mem[x] = sum;return sum;
}
#endif 
int main(void)
{cin >> t;while (t--){cin >> n;for (int i = 1; i <= n; i++)scanf_s("%d", &arr[i]);//memset(mem, 0, sizeof mem);memset(f, 0, sizeof f);for (int i = n; i >= 0; i--){f[i] = max(f[i + 1], f[i + 2] + arr[i]);}//int res = dfs(1);}return 0;
}

四、数字三角形---来自洛谷

还是一样的套路，三种方法解决问题（我希望大家先自己去尝试用这三种方法动手打一下代码，哪里有不明白的直接看代码再自己理解一下，编程还是自己去上手才能看出来明白还是不明白）

1.用暴力搜索dfs

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1005;
int arr[N][N];
int n;
int dfs(int x, int y)
{if (x > n || y > n)return 0;else return max(dfs(x + 1, y) + arr[x][y], dfs(x + 1, y + 1) + arr[x][y]);
}
int main(void)
{cin >> n;for (int i = 1; i <= n; i++){for (int j = 1; j <= i; j++){cin >> arr[i][j];}}int res = dfs(1, 1);cout << res << endl;return 0;
}

2.用记忆化搜索

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1005;
int arr[N][N];
int mem[N][N];
int n;
int dfs(int x, int y)
{if(mem[x][y])return mem[x][y];int sum=0;if (x > n || y > n) sum = 0;else sum = max(dfs(x + 1, y) + arr[x][y], dfs(x + 1, y + 1) + arr[x][y]);mem[x][y]=sum;return sum;
}
int main(void)
{cin >> n;for (int i = 1; i <= n; i++){for (int j = 1; j <= i; j++){cin >> arr[i][j];}}memset(mem,0,sizeof mem);int res = dfs(1, 1);cout << res << endl;return 0;
}

3.递推dp

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1005;
int arr[N][N];
int f[N][N];
int n;
int main(void)
{cin >> n;for (int i = 1; i <= n; i++){for (int j = 1; j <= i; j++){cin >> arr[i][j];}}for (int i = n; i >= 1; i--){for (int j = 1; j <= i; j++){f[i][j] = max(f[i + 1][j] + arr[i][j], f[i + 1] [j + 1] + arr[i][j]);}}cout << f[1][1] << endl;return 0;
}

---

最后：希望读完这篇文章的你，对动态规划有了更深入的了解！