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

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

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

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

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

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

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

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

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

4. 如何利⽤动态规划解决问题
   第⼀种⽅式当然就是记忆化搜索了：

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

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

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

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

1. 状态表⽰：
   dp[i] 表⽰：⾛到第i 个台阶的总⽅案数。
   那最终结果就是在dp[n]处取到。
2. 状态转移⽅程：
   根据最后⼀步划分问题，⾛到第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[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] 。
3. 初始化：
   填i位置的值时，⾄少需要前三个位置的值，因此需要初始化dp[0] = 1, dp[1] = 1, dp[2] = 2，然后从i = 3开始填。
   或者初始化dp[1] = 1, dp[2] = 2, dp[3] = 4，然后从i = 4 开始填。
4. 填表顺序：
   明显是从左往右

#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 65;int n;
LL f[N]; //f[i]表示有i个台阶的时候，一共有多少种方案int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;//初始化f[0] = 1; f[1] = 1; f[2] = 2;for (int i = 3; i <= n; i++){f[i] = f[i - 1] + f[i - 2] + f[i - 3];       }cout << f[n] << endl;return 0;
}

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

#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 [IOI 1994] 数字三角形 Number Triangles - 洛谷

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

1. 状态表⽰：
   dp[i][j] 表⽰：⾛到[i, j] 位置的最⼤权值。
   那最终结果就是在dp 表的第n ⾏中，所有元素的最⼤值。
2. 状态转移⽅程：
   根据最后⼀步划分问题，⾛到[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[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + a[i][j]
3. 初始化：
   因为dp 表被0 包围着，并不影响我们的最终结果，因此可以直接填表。
   思考，如果权值出现负数的话，需不需要初始化？
   ◦ 此时可以全都初始化为$-\infty$ ，负⽆穷⼤在取max 之后，并不影响最终结果。
4. 填表顺序：
   从左往右填写每⼀⾏，每⼀⾏从左往右

#include <bits/stdc++.h>
using namespace std;const int N = 1010;int n;
int a[N][N];
int f[N][N]; //f[i][j]表示从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[i][j];for (int i = 1; i <= n; i++){for (int j = 1; j <= i; j++){f[i][j] = max(f[i-1][j], f[i-1][j-1]) + a[i][j];    }}int ret = 0;for (int j = 1; j <= n; j++){ret = max(ret, f[n][j]);        }cout << ret << endl;return 0;
}

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

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

#include <bits/stdc++.h>
using namespace std;const int N = 1010;int n;
int a[N][N];
int f[N]; //f[i][j]表示从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[i][j];for (int i = 1; i <= n; i++){for (int j = i; j >= 1; j--){f[j] = max(f[j], f[j-1]) + a[i][j];    }}int ret = 0;for (int j = 1; j <= n; j++){ret = max(ret, f[j]);        }cout << ret << endl;return 0;
}