题目.png

当时在遇到这道题的时候，心里想的是。

这多简单啊，不就是一个递归吗？

import java.util.Scanner;

public class Main {
    static int num;

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        String a = cin.next();
        String c = null;
        int b = Integer.decode(a);
        dd(b);
        System.out.println(num + 1);
    }

    public static void dd(int b) {
        for (int i = b / 2; i >= 1; i--) {
            num++;
            dd(i);
        }
    }
}

然后……

图片.png

超时。。。

这是因为之前我们之前用的是深度搜索算法。时间复杂度为

企图暴力破解

在这里我们应该用动态规划

在这里我首先给出一种解法

记忆化搜索

所谓记忆化搜索 就是把过去算过的值储存起来，第二次需要用的时候直接调用，这样就不会浪费时间空间再去算一遍。

如本题，假如数字为6

当左边添加的自然数为3时

会有两个数字，

即 36、136 。

我们下次遇到3的时候就不用递归去算了，直接调用

import java.util.Scanner;

public class Main {

    static int[] arr = new int[10000001];

    @SuppressWarnings("resource")
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        String a = cin.next();
        int b = Integer.decode(a);

        System.out.println(dd(b) + 1);
    }

    public static int dd(int b) {
        int num = 0;
        if (arr[b] != 0) //检查是否算过该值，如算过，则直接返回该值
            return arr[b];
                /*如果没有算过则执行下面的语句*/
        for (int i = b / 2; i >= 1; i--) {
            num++; //加上自己本身
            num += dd(i);//检测当前的满足要求的数
        }
        arr[b] = num;//用数组记录该B值有多少个满足要求的数字。方便下次直接调用
        return num;
    }
}