题目描述
对于一个递归函数 w(a,b,c)
- 如果 a≤0 或 b≤0 或 c≤0 就返回值 1。
- 如果 a>20 或 b>20 或 c>20 就返回 w(20,20,20)
- 如果 a<b 并且 b<c 就返回 w(a,b,c−1)+w(a,b−1,c−1)−w(a,b−1,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)
这是个简单的递归函数，但实现起来可能会有些问题。当 a,b,c 均为 15 时，调用的次数将非常的多。你要想个办法才行。
注意：例如 w(30,−1,0) 又满足条件 1 又满足条件 2，请按照最上面的条件来算，答案为 1。
输入格式
会有若干行。
并以 −1,−1,−1 结束。
输出格式
输出若干行，每一行格式：
w(a, b, c) = ans
注意空格。
题目分析
这道题直接利用题目给出的逻辑返回值会出现超时。
我们利用记忆化搜索来解决问题。
自我理解：记忆化搜索就是在dp的过程中将已经知道的值进行赋值给一个和dp对应的数组中去，在执行程序时候先判断是否对应的值存在，若存在就能直接使用，去除了重复的步骤，极大的减少了程序的运行时间。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
bool visted[30][30][30];
ll w[30][30][30];
ll dp(ll a, ll b, ll c) {
if(a <= 0 || b <= 0 || c <= 0) return 1;
else if (a > 20 || b > 20 || c > 20) {
return (dp(20, 20 ,20));
}
else if (a < b && b < c) {
if(!visted[a][b][c]){
w[a][b][c] = dp(a,b,c-1)+dp(a,b-1,c-1)-dp(a,b-1,c);
visted[a][b][c] = true;
return w[a][b][c];
}else{
return w[a][b][c];
}
}
else{
if(!visted[a][b][c]){
w[a][b][c] = (dp(a-1, b,c) + dp(a-1,b-1,c) + dp(a-1,b,c-1) - dp(a-1,b-1,c-1));
visted[a][b][c] = true;
return w[a][b][c];
}else{
return w[a][b][c];
}
}
}
int main() {
ll a, b , c;
while(cin >> a >> b >> c) {
if(a == -1 && b == -1 && c == -1)break;
printf("w(%ld, %ld, %ld) = %ld\n", a, b , c, dp(a,b,c));
}
return 0;
}