L2-029 特立独行的幸福 (25 分)

题目

题目链接

题解

DFS（记忆化）

说明：一个数如果先转换成了不在范围内的数后最终转换到了1是允许的，即也可以判定为是幸福数。

主要的难点在于如何判断数是否为幸福数、如果是幸福数又如何判断该数是否能由其他幸福数转换而来、统计迭代的次数。

在dfs的过程中通过设置数组标记来解决上面的难点。

代码

#include
using namespace std;
const int N = 1e4+10;
int l, r;
int dp;
int st[N]; // st=-1表示未赋值，st=0表示不是幸福数，st=1表示是幸福数
int vis[N], cnt[N], change[N];

int dfs (int x) {
//	cout > r;
	for (int i = l;i