NO.82十六届蓝桥杯备战|动态规划-从记忆化搜刮到动态规划|下楼梯|数字三角形(C++)
[*]记忆化搜刮
在搜刮的过程中，如果搜刮树中有许多重复的结点，此时可以通过⼀个"备忘录"，记录第⼀次搜刮到的效果。当下⼀次搜刮到这个结点时，直接在"备忘录"⾥⾯找效果。其中，搜刮树中的⼀个⼀个结点，也称为⼀个⼀个状态。
⽐如经典的斐波那契数列题目
int f; // 备忘录
int fib(int n)
{
// 搜索之前先往备忘录⾥⾯瞅瞅
if(f != -1) return f;
if(n == 0 || n == 1) return f = n;
// 返回之前，把结果记录在备忘录中
f = fib(n - 1) + fib(n - 2);
return f;
}
[*]递归改递推
在⽤记忆化搜刮解决斐波那契题目时，如果关注"备忘录"的填写过程，会发现它是从左往右依次填写的。当i位置前⾯的格⼦填写完毕之后，就可以根据格⼦⾥⾯的值计算出i位置的值。所以，整个递归过程，我们也可以改写成循环的形式，也就是递推
int f; // f 表⽰：第 i 个斐波那契数
int fib(int n)
{
// 初始化前两个格⼦
f = 0; f = 1;
// 按照递推公式计算后⾯的值
for(int i = 2; i <= n; i++)
{
f = f + f;
}
// 返回结果
return f;
}
[*]动态规划
动态规划（Dynamic Programming，简称DP）是⼀种⽤于解决多阶段决定题目的算法头脑。它通过将复杂题目分解为更⼩的⼦题目，并存储⼦题目的解（通常称为“状态”），从⽽避免重复计算，提⾼效率。因此，动态规划⾥，蕴含着分治与剪枝头脑。
上述通过记忆化搜刮以及递推解决斐波那契数列的⽅式，着实都是动态规划。
注意：
[*]动态规划中的相关概念着实远不⽌如此，还会有：重叠⼦题目、最优⼦布局、⽆后效性、有向⽆环图等等。
[*]这些概念没有⼀段时间的沉淀是不大概完全理解的。可以等学过⼀段时间之后，再去打仗这些概念。不过，这些概念纵然不懂，也不影响做题~
在递推形式的动态规划中，常⽤下⾯的专有名词来表述：
[*]状态表⽰：指 f 数组中，每⼀个格⼦代表的含义。其中，这个数组也会称为 dp 数组，大概dp 表。
[*]状态转移⽅程：指 f 数组中，每⼀个格⼦是怎样⽤别的的格⼦推导出来的
[*]初始化：在填表之前，根据题⽬中的默认条件大概题目的默认初始状态，将 f 数组中若⼲格⼦先填上值。
着实递推形式的动态规划中的各种表述，是可以对应到递归形式的：
[*]状态表⽰<—>递归函数的意义；
[*]状态转移⽅程<—>递归函数的主函数体；
[*]初始化<—>递归函数的递归出⼝。
[*]怎样利⽤动态规划解决题目
第⼀种⽅式当然就是记忆化搜刮了：
[*]先⽤递归的头脑去解决题目；
[*]如果有重复⼦题目，就改成记忆化搜刮的形式。
第⼆种⽅式，直接使⽤递推形式的动态规划解决：
[*]界说状态表⽰：
⼀般情况下根据履历+递归函数的意义，赋予 dp 数组相应的含义。（着实还可以去蒙⼀个，如果蒙的状态表⽰能解决题目，说明蒙对了。如果蒙错了，再换⼀个试~）
[*]推导状态转移⽅程：
根据状态表⽰以及题意，在 dp 表中分析，当前格⼦怎样通过别的格⼦推导出来。
[*]初始化：
根据题意，先将显⽽易⻅的以及边界情况下的位置填上值。
[*]确定填表顺序：
根据状态转移⽅程，确定按照什么顺序来填表。
[*]确定最终效果：
根据题意，在表中找出最终效果
P10250 下楼梯 - 洛谷
由于上楼和下楼是⼀个可逆的过程，因此我们可以把下楼题目转化成上到第n个台阶，⼀共有多少种⽅案。
解法：动态规划
[*]状态表⽰：
dp 表⽰：⾛到第i 个台阶的总⽅案数。
那最终效果就是在dp处取到。
[*]状态转移⽅程：
根据最后⼀步分别题目，⾛到第i 个台阶的⽅式有三种：
a. 从i - 1 台阶向上⾛1 个台阶，此时⾛到i 台阶的⽅案就是dp ；
b. 从i - 2 台阶向上⾛2 个台阶，此时⾛到i 台阶的⽅案就是dp ；
c. 从i - 3 台阶向上⾛3 个台阶，此时⾛到i 台阶的⽅案就是dp ；
综上所述，dp = dp + dp + dp 。
[*]初始化：
填i位置的值时，⾄少需要前三个位置的值，因此需要初始化dp = 1, dp = 1, dp = 2，然后从i = 3开始填。
大概初始化dp = 1, dp = 2, dp = 4，然后从i = 4 开始填。
[*]填表顺序：
明显是从左往右
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 65;
int n;
LL f; //f表示有i个台阶的时候，一共有多少种方案
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
//初始化
f = 1; f = 1; f = 2;
for (int i = 3; i <= n; i++)
{
f = f + f + f;
}
cout << f << endl;
return 0;
}
动态规划的空间优化：
我们发现，在填写dp的值时，我们仅仅需要前三个格⼦的值，第i-4个及其之前的格⼦的值已经毫⽆⽤处了。因此，可以⽤三个变量记录i位置之前三个格⼦的值，然后在填完i位置的值之
后，滚动向后更新
https://i-blog.csdnimg.cn/direct/824367a6b7924fc392ad052ec7d6d70e.png
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 65;
int n;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
LL a = 1, b = 1, c = 2;
for (int i = 3; i <= n; i++)
{
LL t = a + b + c;
a = b;
b = c;
c = t;
}
if (n == 1) cout << b << endl;
else cout << c << endl;
return 0;
}
P1216 数字三角形 Number Triangles - 洛谷
https://i-blog.csdnimg.cn/direct/c92185f5fea84f00817efe390684faf2.png
学习动态规划最经典的⼊⻔题。
解法：动态规划
[*]状态表⽰：
dp 表⽰：⾛到 位置的最⼤权值。
那最终效果就是在dp 表的第n ⾏中，所有元素的最⼤值。
[*]状态转移⽅程：
根据最后⼀步分别题目，⾛到 位置的⽅式有两种：
a. 从 位置向下⾛⼀格，此时⾛到 位置的最⼤权值就是dp ；
b. 从位置向右下⾛⼀格，此时⾛到 位置的最⼤权值就是dp ；
综上所述，应该是两种情况的最⼤值再加上位置的权值：
dp = max(dp, dp) + a
[*]初始化：
由于dp 表被0 包围着，并不影响我们的最终效果，因此可以直接填表。
思考，如果权值出现负数的话，需不需要初始化？
◦ 此时可以全都初始化为 − ∞ -\infty −∞ ，负⽆穷⼤在取max 之后，并不影响最终效果。
[*]填表顺序：
从左往右填写每⼀⾏，每⼀⾏从左往右
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n;
int a;
int f; //f表示从1，1走到i，j的时候，所有方案数的最大权值
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
cin >> a;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
f = max(f, f) + a;
}
}
int ret = 0;
for (int j = 1; j <= n; j++)
{
ret = max(ret, f);
}
cout << ret << endl;
return 0;
}
动态规划的空间优化：
我们发现，在填写第i ⾏的值时，我们仅仅需要前⼀⾏的值，并不需要第i - 2 以及之前⾏的值。
因此，我们可以只⽤⼀个⼀维数组来记录上⼀⾏的效果，然后在这个数组上更新当前⾏的值
https://i-blog.csdnimg.cn/direct/1795877a0e2145a890259a9688debe6b.png
需要注意，当⽤由于我们当前这个位置的值需要左上⻆位置的值，因此滚动数组优化的时候，要改变第⼆维的遍历顺序
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n;
int a;
int f; //f表示从1，1走到i，j的时候，所有方案数的最大权值
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= i; j++)
cin >> a;
for (int i = 1; i <= n; i++)
{
for (int j = i; j >= 1; j--)
{
f = max(f, f) + a;
}
}
int ret = 0;
for (int j = 1; j <= n; j++)
{
ret = max(ret, f);
}
cout << ret << endl;
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]