记忆化搜索（斐波那契数列+滑雪+电）_记忆化搜索的斐波那契复杂度

使用记忆化搜索必须是拓扑图

斐波那契数列

1.1 问题定义：输入一个正整数n，求斐波那契数列的第n项f(n) 其中 f(0)=f(1)=1,f(n)=f(n-1)+f(n-2)(n>=2)

1.2 问题分析：

新手初学递归时，一般都会有这个例子，并且后续还会学到用迭代代替递归可以大幅优化程序的运行时间。
这是因为递归算法的深度等于输入正整数n，而这样的递归树会有2^n个结点，如图

实际上这样的递归树会有很多重复冗余的计算，比如节点3被计算了2次，节点2被计算了3次，值越小的节点，被重复计算的次数越多。所以用迭代的方式，我们从小到大，先计算f (1)f (2)f (3)  …, 以此类推，最后再由f(n−1)和f(n−2)算出f(n)，这样避免了重复计算，算法的时间复杂度为O(n)。

为了体会记忆化搜索的思想，我们不使用迭代算法来求f(n)，而是用记忆化搜索来优化递归算法。

1.3 普通递归算法
常规的递归算法f i b 1 fib1fib1代码如下：

long long fib(long long n)
{
     if(n<=1) return 1;
     return fib(n-1)+fib(n-2);
}

1.4 记忆化搜索优化后的递归算法
使用记忆化搜索优化递归算法，我们额外开辟一个数组memory来保存递归过程中已求得的结果。f i b 2 fib2fib2代码如下：

#include <iostream>
#include <ctime>
#include <memory.h>

#define MAX_N 1000000

int* memo = (int*)malloc(MAX_N * sizeof(int));
int fib2(int n) {
    if (memo[n] == -1) {
        if (n <= 1) memo[n] = 1;
        else memo[n] = fib2(n - 1) + fib2(n - 2);
    }
    return memo[n];

#include<iostream>
#include<cstring>
#include<algorithm>
const int N=1e6+10;
typedef long long ll;
ll memory[N];
ll fib(ll n)
{
      if(memory[n]==-1)//没有被标记过 需要执行计算出来
{
     if(n<=1) memory[n]=1;
     else memory[n]=fib(n-1)+fib(n-2); 
}
return memory[n];//如果已经被标记过 就可以直接返回了
}
int main()
{
       ll n;scanf("%lld",&n);
      memset(memory,-1,sizeof(memory));
      ll x=fib(n);
      printf("%lld",x);
}

以求解f(5)为例，递归树的节点访问顺序如下图所示。 

我们从节点5开始，依次来到节点4，节点3，节点2，节点1（上图红色节点）。并且在递归返回过程中，节点2，节点3的值被计算出。此时递归返回来到节点4，f ( 4 ) = f ( 3 ) + f ( 2 ) ，如果是一般的递归，此时还需要重新计算f(2)；但在记忆化搜索中，f(2)的值已经被memory[]记录下来了，实际并不需要继续向下递归重复计算，函数可以直接返回。最后，递归返回来到了节点5，本应重复计算的f(3)由于memory[]的记录，也不需要重复计算了。所以，记忆化搜索可以起到 剪枝 的作用，对于已经保存的 中间结果 ，由于其记忆能力，并不需要重新递归计算了。
 

滑雪

给定一个 R 行 C 列的矩阵，表示一个矩形网格滑雪场。

矩阵中第 i 行第j 列的点表示滑雪场的第 i 行第 j 列区域的高度。

一个人从滑雪场中的某个区域内出发，每次可以向上下左右任意一个方向滑动一个单位距离。

当然，一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度。

下面给出一个矩阵作为例子：

 1  2  3  4 5
 
16 17 18 19 6
 
15 24 25 20 7
 
14 23 22 21 8
 
13 12 11 10 9

在给定矩阵中，一条可行的滑行轨迹为 24−17−2−1。

在给定矩阵中，最长的滑行轨迹为 25−24−23−…−3−2−1，沿途共经过 25 个区域。

现在给定你一个二维矩阵表示滑雪场各区域的高度，请你找出在该滑雪场中能够完成的最长滑雪轨迹，并输出其长度(可经过最大区域数)。

输入格式

第一行包含两个整数 R 和 C。

接下来 R 行，每行包含 C 个整数，表示完整的二维矩阵。

输出格式

输出一个整数，表示可完成的最长滑雪长度。

数据范围

1≤R,C≤300
0≤矩阵中整数≤10000

输入样例：

5 5
1 2 3 4 5
16 17 18 19 6
15 24 25 20 7
14 23 22 21 8
13 12 11 10 9

输出样例：

25

 

 

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=330;
int g[N][N];//存储数据 网络滑雪场
int f[N][N];//状态转移方程 用来表示f[i][j],以（i，j)为起点滑雪的路径最长
int n,m;
int dx[4]={0,0,-1,1},dy[4]={1,-1,0,0};
int dp(int x,int y)
{
    int &v=f[x][y];//Y总说的小技巧，等于把f[x][y]简化成了v，如果v发生变化，f[x][y]也会随之变化
    if(v!=-1) return v;//如果别标记过直接返回 说明已经被存储过
    v=1;//若没有 则是v=1 因为从起点开始 就包括一个格子
    for(int i=0;i<4;i++)
    {
        int xx=dx[i]+x,yy=dy[i]+y;
        if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&g[xx][yy]<g[x][y])
        v=max(v,dp(xx,yy)+1); //就相当于取四个方向的路径中的最大值加1
    }
    return v;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    scanf("%d",&g[i][j]);
     
    memset(f,-1,sizeof(f));
    int res=0;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    res=max(res,dp(i,j));//取最大值
    printf("%d\n",res);
    return 0;
}

 电

某城市有 N 个电力节点，编号 1∼N。

这些电力节点形成的电力网络，可以看作一个 N 个节点 N−1 条边的连通图。

每个电力节点都有一个固定的电容，其中第 i 个节点的电容为 Ai。

现在，可以选择其中一个节点进行供电，其它节点也可以根据实际连接以及具体电容情况接收电力。

具体来说，如果第 i 个节点通电，那么它也可以将电力传输给其它所有与它直接连接且电容严格小于 Ai 的节点。

我们希望通过合理选择初始供电节点，从而使得尽可能多的节点能够通电。

请你计算并输出可以通电的最大节点数量。

输入格式

第一行包含整数 T，表示共有 T 组测试数据。

每组数据第一行包含整数 N。

第二行包含 N 个整数 A1,A2,…,AN。

接下来 N−1 行，每行包含两个整数 Xi,Yi，表示节点 Xi和 Yi 之间存在直接连接。

输出格式

每组数据输出一个结果，每个结果占一行。

结果表示为 Case #x: y，其中 x为组别编号（从 1 开始），y 为可以通电的最大节点数量。

数据范围

1≤T≤100,
1≤Ai≤10^9,
1≤Xi,Yi≤N,
一个测试点内最多 15 组数据满足 1≤N≤2×10^5，其余数据满足 1≤N≤10^3。

输入样例：

2
5
1 2 3 4 3
1 3
2 3
4 3
4 5
6
1 2 3 3 1 4
3 1
3 2
3 4
4 5
1 6

输出样例：

Case #1: 5
Case #2: 3

样例解释

在 Case 1 中，最佳方案是给第 4 个节点供电，这样可以将电力传输到所有节点。

注意，如果给第 3 个节点供电，则电力只会传输至第 1,2 个节点，而无法传输至第 4 个节点，这样只有三个节点可以通电。

在 Case 2 中，最佳方案是给第 3 个节点供电，这样可以将电力传输至第 1,2 个节点，但是无法传输至第 4 个节点，因为 A4并不严格小于 A3。

注意，如果给第 6 个节点供电，则电力只会传输至第 1 个节点，如果给第 4 个节点供电，则电力只会传输至第 5 个节点。

其实构造一棵数并且是通过判读 把它当成单项边 因为只有 Ai>Aj 并且有边才能通 并且是拓扑图与滑雪证明方法相似

动态规划
状态定义：dp[i]表示以第i个节点为根的最大连通分量大小。
状态转移方程：dp[i]=1+Σdp[j]（其中j为i的子节点）

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=2e5+10,M=2*N;
int h[N],e[M],ne[M],idx;
int w[N];
int f[N];
//构造图
void add(int a,int b)
{
     e[idx]=b;
     ne[idx]=h[a];
     h[a]=idx++;
}
int dp(int u)
{
    if(f[u]!=-1) return f[u];
    f[u]=1;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(w[j]<w[u]) f[u]+=dp(j);
    }
    return f[u];
}
 
int main()
{
    int t;scanf("%d",&t);
    for(int k=1;k<=t;k++)
    {
        int n;scanf("%d",&n);
        for(int i=1;i<=n;i++)
        scanf("%d",&w[i]);
        memset(h,-1,4*(n+1));//记住要重新初始化
        idx=0;
        for(int i=1;i<n;i++)
        {
            int a,b;scanf("%d%d",&a,&b);
            add(a,b);
            add(b,a);
        }
        int res=0;
        memset(f,-1,4*(n+1));//重新初始化
        for(int i=1;i<=n;i++)
        res=max(res,dp(i));
        printf("Case #%d: %d\n",k,res);
    }
}