思路其实挺简单的：

    1. 当数为偶数时，dp[i] = dp[i / 2]，当为奇数时，dp[i] = dp[i - 1] + 1

      1. class Solution {
      2.  public int[] countBits(int n) {
      3.      // dp[i] 表示n所对应的1的数量
      4.      int[] dp = new int[n + 1];
      6.      for (int i = 1; i <= n; i++) {
      7.          if ((i & 1) == 0) {
      8.              // odd
      9.              dp[i] = dp[i / 2];
      10.          } else {
      11.              dp[i] = dp[i - 1] + 1;
      12.          }
      13.      }
      14.      // printArr(dp);
      15.      return dp;
      16.  }
      18.  private void printArr(int[] arr) {
      19.      for (int i : arr) {
      20.          System.out.print(i + " ");
      21.      }
      22.  }
      23. }