DP or greedy?

Give an integer N, N>0. We can have three possible operations:

n-1,

n/2

n/3

For division, we must guarantee the reminder is 0.

What is the minimum number of operations to achieve 1?

DP is shown above

We can use DP to solve this problem with complexity of O(n)

Greedy and DP code are given below.

def dp(n):
    if n<=3:return 1
    d = [0]*(n+1)
    for k in range(n-1,0,-1):
        print("k: ",k)
        this_res = d[k+1]+1
        if 2*k<=n:
            if d[2*k]+1<this_res:
                print("2")
                this_res = d[2*k]+1
        if 3*k<=n:
            if d[3*k]+1<this_res:
                print("3")
                this_res = d[3*k]+1
        #if 3*k<=n:this_res = min(this_res, d[3*k]+1)
        d[k] = this_res
    return d[1]
def greedy(n):
    if n<=3:return 1
    res = 0
    while n!=1:
        if n%3==0:
            n=n//3
        elif n%2==0:
            n= n//2
        else:n-=1
        res+=1
    return res
if __name__ == '__main__':
    #N=1000000
    N=1000
    for n in range(9, 15):
        if dp(n)!=greedy(n):
            print("dp and greedy does not agree with each other, dp: ", n, dp(n), "greedy: ", greedy(n))
            break
    print("Done")

Greedy is INCORRECT. Such as when N=10, DP got 3:

10–1=9, 9/3=3, 3/3=1

While greedy got 4.