Codeforces - Nirvana

제목 링크: Codeforces - Nirvana
폭발 수색 혹은 디지털 dp와 유사하다.
현재 이 사람이 9를 얻을 수 있는지 없는지를 매거한 다음에 9를 가져갈 수 있는지 없는지를 나눈다.
AC 코드:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include
//#define int long long
using namespace std;
int n,a[20],cnt,dp[20][2];
int dfs(int pos,int lim){
     
	if(!pos) return 1;
	if(!lim&&dp[pos][lim]!=-1) return dp[pos][lim];
	if(lim) dp[pos][lim]=max(dfs(pos-1,1)*max(1,a[pos]),dfs(pos-1,0)*max(1,a[pos]-1));
	else dp[pos][lim]=dfs(pos-1,0)*9;
	return dp[pos][lim];
}
signed main(){
     
	cin>>n; memset(dp,-1,sizeof dp);
	while(n) a[++cnt]=n%10,n/=10;
	cout<<dfs(cnt,1);
	return 0;
}