NO.82十六届蓝桥杯备战|动态规划-从记忆化搜刮到动态规划|下楼梯|数字三角 ...

• 记忆化搜刮
  在搜刮的过程中，如果搜刮树中有许多重复的结点，此时可以通过⼀个"备忘录"，记录第⼀次搜刮到的效果。当下⼀次搜刮到这个结点时，直接在"备忘录"⾥⾯找效果。其中，搜刮树中的⼀个⼀个结点，也称为⼀个⼀个状态。
  ⽐如经典的斐波那契数列题目
  

1. int f[N]; // 备忘录  
3. int fib(int n)  
4. {  
5.         // 搜索之前先往备忘录⾥⾯瞅瞅  
6.         if(f[n] != -1) return f[n];  
7.         if(n == 0 || n == 1) return f[n] = n;  
8.        
9.         // 返回之前，把结果记录在备忘录中  
10.         f[n] = fib(n - 1) + fib(n - 2);  
11.         return f[n];  
12. }

复制代码

• 递归改递推
  在⽤记忆化搜刮解决斐波那契题目时，如果关注"备忘录"的填写过程，会发现它是从左往右依次填写的。当i位置前⾯的格⼦填写完毕之后，就可以根据格⼦⾥⾯的值计算出i位置的值。所以，整个递归过程，我们也可以改写成循环的形式，也就是递推
  

1. int f[N]; // f[i] 表⽰：第 i 个斐波那契数  
2. int fib(int n)  
3. {  
4.         // 初始化前两个格⼦  
5.         f[0] = 0; f[1] = 1;  
6.        
7.         // 按照递推公式计算后⾯的值  
8.         for(int i = 2; i <= n; i++)  
9.         {  
10.                 f[i] = f[i - 1] + f[i - 2];  
11.         }  
12.        
13.         // 返回结果  
14.         return f[n];  
15. }

复制代码

• 动态规划
  动态规划（Dynamic Programming，简称DP）是⼀种⽤于解决多阶段决定题目的算法头脑。它通过将复杂题目分解为更⼩的⼦题目，并存储⼦题目的解（通常称为“状态”），从⽽避免重复计算，提⾼效率。因此，动态规划⾥，蕴含着分治与剪枝头脑。
  上述通过记忆化搜刮以及递推解决斐波那契数列的⽅式，着实都是动态规划。
  注意：
  

• 动态规划中的相关概念着实远不⽌如此，还会有：重叠⼦题目、最优⼦布局、⽆后效性、有向⽆环图等等。
  
• 这些概念没有⼀段时间的沉淀是不大概完全理解的。可以等学过⼀段时间之后，再去打仗这些概念。不过，这些概念纵然不懂，也不影响做题~
  在递推形式的动态规划中，常⽤下⾯的专有名词来表述：
  

• 状态表⽰：指 f 数组中，每⼀个格⼦代表的含义。其中，这个数组也会称为 dp 数组，大概dp 表。
  
• 状态转移⽅程：指 f 数组中，每⼀个格⼦是怎样⽤别的的格⼦推导出来的
  
• 初始化：在填表之前，根据题⽬中的默认条件大概题目的默认初始状态，将 f 数组中若⼲格⼦先填上值。
  着实递推形式的动态规划中的各种表述，是可以对应到递归形式的：
  

• 状态表⽰<—>递归函数的意义；
  
• 状态转移⽅程<—>递归函数的主函数体；
  
• 初始化<—>递归函数的递归出⼝。
  

• 怎样利⽤动态规划解决题目
  第⼀种⽅式当然就是记忆化搜刮了：
  

• 先⽤递归的头脑去解决题目；
  
• 如果有重复⼦题目，就改成记忆化搜刮的形式。
  第⼆种⽅式，直接使⽤递推形式的动态规划解决：
  

• 界说状态表⽰：
  ⼀般情况下根据履历+递归函数的意义，赋予 dp 数组相应的含义。（着实还可以去蒙⼀个，如果蒙的状态表⽰能解决题目，说明蒙对了。如果蒙错了，再换⼀个试~）
  
• 推导状态转移⽅程：
  根据状态表⽰以及题意，在 dp 表中分析，当前格⼦怎样通过别的格⼦推导出来。
  
• 初始化：
  根据题意，先将显⽽易⻅的以及边界情况下的位置填上值。
  
• 确定填表顺序：
  根据状态转移⽅程，确定按照什么顺序来填表。
  
• 确定最终效果：
  根据题意，在表中找出最终效果
  

P10250 [GESP样题 六级] 下楼梯 - 洛谷

由于上楼和下楼是⼀个可逆的过程，因此我们可以把下楼题目转化成上到第n个台阶，⼀共有多少种⽅案。
解法：动态规划

• 状态表⽰：
  dp 表⽰：⾛到第i 个台阶的总⽅案数。
  那最终效果就是在dp[n]处取到。
  
• 状态转移⽅程：
  根据最后⼀步分别题目，⾛到第i 个台阶的⽅式有三种：
  a. 从i - 1 台阶向上⾛1 个台阶，此时⾛到i 台阶的⽅案就是dp[i - 1] ；
  b. 从i - 2 台阶向上⾛2 个台阶，此时⾛到i 台阶的⽅案就是dp[i - 2] ；
  c. 从i - 3 台阶向上⾛3 个台阶，此时⾛到i 台阶的⽅案就是dp[i - 3] ；
  综上所述，dp = dp[i - 1] + dp[i - 2] + dp[i - 3] 。
  
• 初始化：
  填i位置的值时，⾄少需要前三个位置的值，因此需要初始化dp[0] = 1, dp[1] = 1, dp[2] = 2，然后从i = 3开始填。
  大概初始化dp[1] = 1, dp[2] = 2, dp[3] = 4，然后从i = 4 开始填。
  
• 填表顺序：
  明显是从左往右
  

1. #include <bits/stdc++.h>
2. using namespace std;
4. typedef long long LL;
6. const int N = 65;
8. int n;
9. LL f[N]; //f[i]表示有i个台阶的时候，一共有多少种方案
11. int main()
12. {
13.     ios::sync_with_stdio(false);
14.     cin.tie(0);
16.     cin >> n;
18.     //初始化
19.     f[0] = 1; f[1] = 1; f[2] = 2;
21.     for (int i = 3; i <= n; i++)
22.     {
23.         f[i] = f[i - 1] + f[i - 2] + f[i - 3];      
24.     }
26.     cout << f[n] << endl;
27.    
28.     return 0;
29. }

复制代码

动态规划的空间优化：
我们发现，在填写dp的值时，我们仅仅需要前三个格⼦的值，第i-4个及其之前的格⼦的值已经毫⽆⽤处了。因此，可以⽤三个变量记录i位置之前三个格⼦的值，然后在填完i位置的值之
后，滚动向后更新

1. #include <bits/stdc++.h>
2. using namespace std;
4. typedef long long LL;
6. const int N = 65;
8. int n;
10. int main()
11. {
12.     ios::sync_with_stdio(false);
13.     cin.tie(0);
15.     cin >> n;
17.     LL a = 1, b = 1, c = 2;
19.     for (int i = 3; i <= n; i++)
20.     {
21.         LL t = a + b + c;
22.         a = b;
23.         b = c;
24.         c = t;
25.     }
27.     if (n == 1) cout << b << endl;
28.     else cout << c << endl;
29.    
30.     return 0;
31. }

复制代码

P1216 [IOI 1994] 数字三角形 Number Triangles - 洛谷

学习动态规划最经典的⼊⻔题。
解法：动态规划

• 状态表⽰：
  dp[j] 表⽰：⾛到[i, j] 位置的最⼤权值。
  那最终效果就是在dp 表的第n ⾏中，所有元素的最⼤值。
  
• 状态转移⽅程：
  根据最后⼀步分别题目，⾛到[i, j] 位置的⽅式有两种：
  a. 从[i - 1, j] 位置向下⾛⼀格，此时⾛到[i, j] 位置的最⼤权值就是dp[i - 1][j] ；
  b. 从[i - 1, j - 1]位置向右下⾛⼀格，此时⾛到[i, j] 位置的最⼤权值就是dp[i - 1][j - 1] ；
  综上所述，应该是两种情况的最⼤值再加上[i,j]位置的权值：
  dp[j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[j]
  
• 初始化：
  由于dp 表被0 包围着，并不影响我们的最终效果，因此可以直接填表。
  思考，如果权值出现负数的话，需不需要初始化？
  ◦ 此时可以全都初始化为                                        −                            ∞                                  -\infty                     −∞ ，负⽆穷⼤在取max 之后，并不影响最终效果。
  
• 填表顺序：
  从左往右填写每⼀⾏，每⼀⾏从左往右
  

1. #include <bits/stdc++.h>
2. using namespace std;
4. const int N = 1010;
6. int n;
7. int a[N][N];
8. int f[N][N]; //f[i][j]表示从1，1走到i，j的时候，所有方案数的最大权值
10. int main()
11. {
12.     ios::sync_with_stdio(false);
13.     cin.tie(0);
15.     cin >> n;
17.     for (int i = 1; i <= n; i++)
18.         for (int j = 1; j <= i; j++)
19.             cin >> a[i][j];
21.     for (int i = 1; i <= n; i++)
22.     {
23.         for (int j = 1; j <= i; j++)
24.         {
25.             f[i][j] = max(f[i-1][j], f[i-1][j-1]) + a[i][j];   
26.         }
27.     }
29.     int ret = 0;
30.     for (int j = 1; j <= n; j++)
31.     {
32.         ret = max(ret, f[n][j]);        
33.     }
34.     cout << ret << endl;
35.    
36.     return 0;
37. }

复制代码

动态规划的空间优化：
我们发现，在填写第i ⾏的值时，我们仅仅需要前⼀⾏的值，并不需要第i - 2 以及之前⾏的值。
因此，我们可以只⽤⼀个⼀维数组来记录上⼀⾏的效果，然后在这个数组上更新当前⾏的值

需要注意，当⽤由于我们当前这个位置的值需要左上⻆位置的值，因此滚动数组优化的时候，要改变第⼆维的遍历顺序

1. #include <bits/stdc++.h>
2. using namespace std;
4. const int N = 1010;
6. int n;
7. int a[N][N];
8. int f[N]; //f[i][j]表示从1，1走到i，j的时候，所有方案数的最大权值
10. int main()
11. {
12.     ios::sync_with_stdio(false);
13.     cin.tie(0);
15.     cin >> n;
17.     for (int i = 1; i <= n; i++)
18.         for (int j = 1; j <= i; j++)
19.             cin >> a[i][j];
21.     for (int i = 1; i <= n; i++)
22.     {
23.         for (int j = i; j >= 1; j--)
24.         {
25.             f[j] = max(f[j], f[j-1]) + a[i][j];   
26.         }
27.     }
29.     int ret = 0;
30.     for (int j = 1; j <= n; j++)
31.     {
32.         ret = max(ret, f[j]);        
33.     }
34.     cout << ret << endl;
35.    
36.     return 0;
37. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。