• + 1 comment

    Here is my DP solution (C# code). Take a look:

    public static int DownToZero(int n) {
        return new DownToZeroSolution().Solve(n);
    }
        
    class DownToZeroSolution {
        static int calculated_N;
        static readonly int[] solutions;
    
        static DownToZeroSolution() {
            calculated_N = 1;
            solutions = new int[1_000_001];
            solutions[1] = 1;
        }
        public int Solve(int n) {
            if(n <= calculated_N) return solutions[n];
    
            for(int i = calculated_N + 1; i <= n; i++) {
                solutions[i] = CalculateItem(i);
            }
            calculated_N = n;
            return solutions[n];
        }
        static int CalculateItem(int n) {
            int min = solutions[n - 1];
            int d_start;
            int d_step;
    
            if((n & 1) == 1) {
                d_start = 3;
                d_step = 2;
            }
            else {
                d_start = 2;
                d_step = 1;
            }
            
            int topN = (int)(Math.Sqrt(n) + 0.1);
    
            // n = d1*d2
            for(int d1 = d_start; d1 <= topN; d1 += d_step) {
                if(n % d1 == 0)
                    min = Math.Min(min, solutions[Math.Max(d1, n / d1)]);
            }
            return 1 + min;
        }
    }