本文共 1079 字，大约阅读时间需要 3 分钟。

为了解决这个问题，我们需要计算给定范围内每个数字的二进制表示中1的数量。通过动态规划，我们可以在O(n)的时间复杂度内完成这个任务，同时保持空间复杂度为O(n)。

方法思路

我们可以利用动态规划来解决这个问题。对于每个数字i：

这种方法的时间复杂度为O(n)，因为我们只需要遍历每个数字一次。空间复杂度为O(n)，因为我们使用了一个大小为n+1的数组来存储中间结果。

解决代码

public class Solution338 {    public static int[] countBits(int num) {        int[] dp = new int[num + 1];        dp[0] = 0;        for (int i = 1; i <= num; i++) {            if (i % 2 == 1) {                dp[i] = dp[i - 1] + 1;            } else {                dp[i] = dp[i / 2];            }        }        return dp;    }    public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        int x = sc.nextInt();        int[] dp = countBits(x);        for (int i = 0; i <= x; i++) {            System.out.print(dp[i] + " ");        }    }}

代码解释

这种方法高效且直接，能够在O(n)的时间内完成任务，同时保持了较低的空间复杂度。