Python3, 197 bytes

S=sorted
def f(n):
 q=[(n,[])]
 while q:
  (n,b),*q=S(q,key=lambda x:x[0])
  if 0==n:return len(b)
  for j in S({k*t for k in[1,9,81]for t in range(1,65)},reverse=True):
   if j<=n:q+=[(n-j,b+[j])]

Try it online!

Wolfram Language (Mathematica), 66 bytes

Min[Length/@IntegerPartitions[#,All,Union[#,9#,81#]&@Range@64,#]]&

Try it online!

05AB1E, 30 27 bytes

ŽK≠‰`91vDy64*›i1sy9*%]64/îO

Try it online! or verify all test cases

-3 bytes thanks to Kevin Cruijssen

This is my first 05AB1E submission, so I am sure that this can be optimized.

JavaScript (ES6), 72 66 57 56 bytes

Saved 1 byte thanks to @nwellnhof

f=n=>n&&1+f(n<5184?n>64&&n%(n<576?9:n>719?81:72):n-5184)

Try it online!

Perl 6, 47 bytes

{+($_,(*X-(1,9,81 X*^65)).grep(*>=0).min...^0)}

Try it online!

A greedy algorithm seems to work.

Jelly, 17 bytes

64R×9;Ɗ⁺ff€¥@ŒṗẈṂ

Try it online!

-1 thanks to Jonathan Allan.

Explanation (you can't test for inputs larger than 58 over TIO):

64R×9;Ɗ⁺ff€¥@ŒṗẈṂ Arguments: x
64R               [1..64]
   ×9;Ɗ           Multiply by 9, prepend to original list
       ⁺          Do the above once more
             Œṗ   Positive integer partitions of x
           ¥@     Call with reversed arguments (x = partitions, y = flattened outer product)
         f€         For each partition in x, keep the elements that are in y
        f           Keep the elements of x that have remained intact after the above
               Ẉ  Lengths of the remaining partitions
                Ṃ Minimum