当前位置：首页 > article >正文

算法题（107）：function

article 2025/3/29 17:25:54

审题：

本题需要我们根据题目写出递归函数，并返回递归结果

时间复杂度：本题的数据范围虽然很大，但是由于条件2的限制，数据量可以看成是20，于是我们就可以使用递归函数了

思路：
方法一：记忆化搜索

经过分析我们可知：本题会出现完全重复的递归，所以我们需要使用备忘录对已经知道结果的递归结果记录，每次进入递归时要记得查找备忘录

解题：
#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
ll a,b,c;
const int N = 25;
ll f[N][N][N];//备忘录
（1）main函数
int main() 
{
    memset(f, -1, sizeof(f));
    while (cin >> a >> b >> c) {
        if (a == -1 && b == -1 && c == -1) break;//结束数据录入
        printf("w(%lld, %lld, %lld) = %lld\n", a, b, c, w(a, b, c));
    }
    return 0;
}
(2)dfs递归函数
ll w(ll a, ll b, ll c)
 {
//条件1特殊处理
    if (a <= 0 || b <= 0 || c <= 0) return 1;
//不用记录任意大于20的递归结果
    if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);
//查找备忘录
    if (f[a][b][c] != -1) return f[a][b][c];
    if (a < b && b < c)
    {
        f[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
    } 
    else
    {
    f[a][b][c] = w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a-1,b-1,c-1);
    }
    return f[a][b][c];
}
注意：

1.之所以不用记录大于20的情况的递归结果，是因为他们的结果都是w(20,20,20),后面会记录到备忘录中。

！！！！！！！！！！！！！！：本题的输出格式一定要严格控制，否则答案会全错，空格不要多打或漏打

P1464 Function - 洛谷