#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[20],f[N];
int main()
{
	int n;scanf("%d",&n);int l=1;a[l]=1;
	for(int i=6;i<=n;i*=6)a[++l]=i;
	for(int i=9;i<=n;i*=9)a[++l]=i;
	sort(a+1,a+l+1);int m=unique(a+1,a+l+1)-a-1;
	f[0]=0;for(int i=1;i<=n;i++)f[i]=20;
	for(int i=1;i<=m;i++)for(int j=a[i];j<=n;j++)
		f[j]=min(f[j],f[j-a[i]]+1);
	printf("%d\n",f[n]);return 0;
}

经典的完全背包 （动态规划）

#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 100005;
int dp[MAXN];
int main()
{
   int N;
   cin >> N;
   memset(dp, 0x3f, sizeof(dp));
   dp[0] = 0;
   vector<int> coins;
   coins.push_back(1);
   long long power = 1;
   while(power<=N)
   {
   	    coins.push_back((int)power);
   	    power*=6;
   } 
   power = 1;
   while(power<=N)
   {
   	    coins.push_back((int)power);
   	    power*=9;
   } 
   for(int i = 1;i<=N;i++)
   {
   	    for(int j = 0;j<=coins.size();j++){
   	    	int w = coins[j];
   	    	if(w<=i){
   	    		dp[i] = min(dp[i], dp[i-w]+1);
			   }
		   }
   }
   cout << dp[N];
   return 0;
}