据说一切动态规划都可以用dfs+记忆化来解决,而且能很好的平衡时空复杂度
那么动态规划和递归的关系是什么?老生常谈的自顶向下、自底向上又是什么?
我觉得这篇回答挺不错的大家可以看看。
https://www.zhihu.com/question/410196236
看完回来点赞啊小伙伴们
https://www.zhihu.com/question/410196236
看完回来点赞啊小伙伴们
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int primes[9] = {2,3,5,7,11,13,17,19,23};
// 最多是九个
typedef long long LL;
int maxd;// maxd是最大约数个数
int number;// number 是数本身
int n;
void dfs(int u, int last, int p, int s)//u是第几个素数,last是次数,p是乘积本身,s是约数个数
{
if (s > maxd || s == maxd && p < number) // 当前的约数个数大于或等于最大约数个数&&p小于数本身
{
// 需更新一下
maxd = s;
number = p;
}
if (u == 9) return; // 如果全部枚举一遍了 就退出
for (int i = 1; i <= last; i ++ )//枚举次数
{
if ((LL)p * primes[u] > n) break; // 如果当前素数乘p大于n就退出
p *= primes[u];
dfs(u + 1, i, p, s * (i + 1));
}
}
int main()
{
cin >> n;
dfs(0, 30, 1, 1);
cout << number;
}