题解 | #拼凑硬币#

借鉴了讨论区各位的思路

设 $f (n)$ ：凑出n元的方案数

情况1：n是奇数

n为奇数，则必然需要一个1元钱（不论用哪个一元钱都是一样的；另一个1元必然不用），则 $f (n) = f (n - 1)$

对偶数 $f (n - 1)$ ：用2、2、4、4、8、8 等凑出n-1元，那么形成一个方程：

$n-1=2x_1+2x_2+4x_3+4x_4+ \cdots$ $x_{i}$ 的取值要么为1，要么为0

方案数就是由 $x_{i}$ 构成的不同的解向量 $[x_1,x_2,x_3,\cdots]^T$ 的个数

等式两边除以2，对解空间无影响

因此， $f (n) = f (n - 1) = f ((n - 1) / 2) = f (n / 2) = f (n > > 1)$

情况2：n是偶数

n为偶数，根据是否使用两个1元钱，有两种方案

方案1：不使用两个1元钱

那么有方程： $n = 2x_1+2x_2+4x_3+4x_4+\cdots$

两边除以2对结果无影响

$f (n) = f (n > > 1)$

方案2：使用两个一元钱

方程： $n=1+1+2x_1+2x_2+4x_3+4x_4+\cdots$

两边除以2对结果无影响

$f (n) = f (n - 2) = f ((n - 2) / 2) = f ((n > > 1) - 1)$

但方案1和方案2里面的 $f (n)$ 是在不同前提条件下的方案数，因此归属到n是偶数这种情况下，总的方案数为：

$f (n) = f (n > > 1) + f [(n > > 1) - 1]$

在n不太大的情况下用数组：

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    while (scanner.hasNextInt()) {
        int n = scanner.nextInt();
        System.out.println(numberOfScheme(n));
    }
}

private static int numberOfScheme(int n) {
    int[] dp = new int[n + 1];
    //初始值  dp[0]不要了
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++) {
        if (isOdd(i)) {
            dp[i] = dp[i >> 1];
        } else {
            dp[i] = dp[i >> 1] + dp[(i >> 1) - 1];
        }
    }
    return dp[n];
}

/**
 * 是否是偶数
 */
private static boolean isEven(int i) {
    return ((i & 1) == 0);
}

/**
 * 是否是奇数
 */
private static boolean isOdd(int i) {
    return ((i & 1) == 1);
}

n比较大，用long和map：

public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    Map<Long, Long> map = new HashMap<>();
    map.put(1L,1L);
    map.put(2L,2L);
    while (scanner.hasNextLong()) {
        long n = scanner.nextLong();
        System.out.println(numberOfSchemev2(n, map));
    }
}

private static long numberOfSchemev2(long n, Map<Long, Long> map) {
    if (map.containsKey(n)) {
        return map.get(n);
    }
    long number = 0L;
    if (isOdd(n)) {
        number = numberOfSchemev2(n >> 1, map);
    } else {
        number = numberOfSchemev2(n >> 1, map) + numberOfSchemev2((n >> 1) - 1, map);
    }
    map.put(n, number);
    return number;
}

/**
 * 是否是偶数
 */
private static boolean isEven(long i) {
    return ((i & 1) == 0);
}

/**
 * 是否是奇数
 */
private static boolean isOdd(long i) {
    return ((i & 1) == 1);
}