C++|递推，记忆化搜索，分治(7)
一、递推算法
1.1 简介
递推算法大家肯定都很熟悉。它和递归算法名字相近，但它们有所不同：递推算法它运行效率高，而且代码量还少；但是递归算法的代码较多，它的效率也不怎么高，可能会“Time Limit Exceeded”，一不小心还有可能爆栈（Memory Limit Exceeded）。
1.2 方法
1.2.1 顺推法 从已知的条件出发，逐步推算出要解决的方法（数学公式）。
1.2.2 逆推法 从结果出发，用迭代法推算出问题开始的答案（数学公式）。
*两种方法的实现方法相似，但思路不同
1.3 例题&代码
题目
数塔问题 如图所示为一个数字三角形，请编程计算从顶到底的某处的一条路径，使该路径经过的数字总和最大，只要求输出总和。输入格式
文章图片
第1行，输入一个正整数n；第2行到第n+1行，输入一个三角形。输出格式
输出一个数，代表最大路径组合。样例输入
5样例输出
7
3 8
8 0 1
2 7 4 4
4 5 2 6 5
30数据规模与约定 保证所有数据：
0
---------------------------------------------------------------------------------------------------------------------------
代码 1.顺推法
#include
using namespace std;
int a[101][101];
int main()
{
int n;
cin>>n;
for(int i=1;
i<=n;
i++)
{
for(int j=1;
j<=i;
j++)
{
cin>>a[i][j];
}
}
for(int i=n-1;
i>=1;
i--)
{
for(int j=1;
j<=i;
j++)
{
a[i][j]+=max(a[i+1][j],a[i+1][j+1]);
}
}
cout< 代码说明：从n-2行开始，依次向上计算每个数的第i-1行所对应的两个数（i+1,j 和 i+1,j+1）相加的和。
2.逆推法
#include
using namespace std;
int a[101][101],maxn;
int main()
{
int n;
cin>>n;
for(int i=1;
i<=n;
i++)
{
for(int j=1;
j<=i;
j++)
{
cin>>a[i][j];
}
}
for(int i=2;
i<=n;
i++)
{
for(int j=1;
j<=i;
j++)
{
a[i][j]+=max(a[i-1][j],a[i-1][j-1]);
}
}
for(int i=1;
i<=n;
i++)
maxn=max(maxn,a[n][i]);
cout< 代码说明：从2行开始，依次向下计算每个数的第i+1行所对应的两个数（i-1,j 和 i-1,j-1）相加的和。
二、记忆化搜索 2.1 简介
记忆化搜索算法中综合运用了两个知识点：递归和递推。这种方法用起来比较方便（我觉得没有递推方便，嘻嘻！）。
2.2 常见题目
上楼梯 一个含有n阶的楼梯，一次可以走1阶或2阶，从底走到顶一共有几种走法？
（n<=90）
拍卖 一般情况下，拍卖行的拍卖师在拍卖商品的时候都是从低价开始起拍，由买方报价，最后谁出的价格高，商品就归谁所有。但有个拍卖行，拍卖师在拍卖商品时正好相反：总是从高价开始起拍，如果没有人举成交牌就降价，而且拍卖师在降价时还有规律：假如第i次报价为w元，那么第i+1次报价为w-a或者w-b元，如果降到p元时，你认为价格合适，赶快第一个举成交牌，你就花p元买下了商品。代码
任务：拍卖师把商品从w元降到p元的方法总数。
1.上楼梯
文章图片
2.拍卖
文章图片
三、分治 3.1 简介
在我还没有开始学的时候，总觉得算法是一个及其高级的玩意儿，有种不敢碰它的感觉（包括 分治算法 在内）。可是学了之后。。。这也没有什么special的。
分治算法顾名思义就是分而治之的意思。主体思想呢就是把一件大的事情分开来做（计算）。其实，就和小学学的数学广角——找次品问题雷同。比如：
一共有8枚硬币，其中有一枚硬币是假币。现在用天平称，最少称多少次把假币找出？*这道题就是先把天平的美易边放上4枚硬币，称出假币在哪4枚中。再把这4枚分成2枚2枚的，继续称。接着找到有假币的那一边，继续称最后就能找到。
在分治算法中最常见的方法是二分法。二分法可以运用在许多程序中，比如：归并排序 等等。
3.2 例题&代码
题目
桐桐查单词 今天桐桐接到一个任务，就是把一篇英语文章翻译成中文。对桐桐来说，这任务实在太艰巨了，可怜的桐桐只好拿着英文字典一句句慢慢翻译起来。希望桐桐能在规定的时间内完成任务吧。输入格式
第1行一个整数n，表示字典中一共有多少单词。输出格式
接下来每两行表示一个单词，其中：
第1行是长度<=100的字符串，表示这个单词，全部字母小写，单词不会重复。
第2行是一个整数，表示这个单词在字典中的页码。
接下来一行是一个整数m，表示要查单词数。
接下来m行，每行一个字符串，表示要查的单词，保证在字典中存在。
m行，每行一个整数，表示i个单词在字典中的页数。样例输入
2输出格式
scan
10
word
15
2
scan
word
10数据规模与约定 全部数据保证：
15
n<=20000
m<=10000
---------------------------------------------------------------------------------------------------------------------------
代码
文章图片
文章图片
THE END 好了，今天就说到这儿吧（毕竟我才学到这儿呀，嘿嘿嘿）
今天我是第一次写博客，如写得不好，敬请理解！！！
如果觉得我写的有用，请多留意我日后的博客。
【C++|递推，记忆化搜索，分治(7)】*题目均来自JZOJ网站（39.98.198.136），照片均来自老师PPT
推荐阅读
- 四首关于旅行记忆的外文歌曲
- opencv|opencv C++模板匹配的简单实现
- 记忆中的冬季战场
- 【学生作品】温暖的记忆
- 不让记忆、感觉、情绪成为孩子的负累|不让记忆、感觉、情绪成为孩子的负累|《全脑教养法》（四）
- C语言学习|第十一届蓝桥杯省赛 大学B组 C/C++ 第一场
- 如何摆脱鱼的记忆（）
- 你是否也是一道风景（）
- 珍藏青春的记忆
- c++基础概念笔记