题目链接：https://leetcode.cn/problems/counting-bits/。这道题虽然带有动态规划的 tag，但是只有一个维度的规划很适合刚接触这个概念的新人。
动态规划比较关键的一点是把问题拆分成前面解决过的子问题，这样才能利用前面做过的运算，降低复杂度的同时也节省了时间。首先看下 0-9 的二进制形式来找下规律：
| 十进制 | 二进制（1 的个数） | 十进制 | 二进制（1 的个数） |
| 0 | 0（0） | 5 | 101（2） |
| 1 | 1（1） | 6 | 110（2） |
| 2 | 10（1） | 7 | 111（3） |
| 3 | 11（2） | 8 | 1000（1） |
| 4 | 100（1） | 9 | 1001（2） |
比较容易发现的情况是如果一个数字是 2 的 n 次幂（黄色部分），那么这个数字的二进制表示会比前一个数字进一位，并且其中只有一个 1。这就导致了二进制表示中 1 的个数并不是个持续增长的过程，而是会反复波折，增长一些后会回到 1 重新开始。我的思路是把这种情况当作特例单独处理，对当前的数字进行判断，如果是 2 的 n 次幂就手动将这个数字二进制中 1 的个数赋成 1。
将不容易归纳出递推关系的部分（2 的 n 次幂）去掉后再进行分析。可以发现从数字 4 到 7 的时候最高位的 1 已经固定，低的 2 位的递增过程其实就是 4 前面的所有数字（1-3）的递增过程（因为到 4 的时候二进制才变成 3 位）。同理可以发现数字 8 到 15 的时候最高位的 1 已经固定，低的 3 位的递增过程就是 8 前面的所有数字（1-7）的递增过程。这样就构成了一个递推关系，比如在计算 m = 13（二进制表示为1101）时，就可以先减去距离最近的 2 的 n 次幂（也就是 8），这样就去掉了最高位的 1，剩下的 5 的二进制表示也已经计算过了可以直接用。
整个算法中还有一个需求就是判断某个数是不是 2 的 n 次幂以及某个数最接近的 2 的 n 次幂是什么。由于整个计算过程是递增的，我们可以直接用一个变量来记录，额外的空间开销就是 \(O(1)\)。
用这种思路的实现如下：
class Solution {
public:
vector<int> countBits(int n) {
vector<int> ans(n + 1);
ans[0] = 0;
int num = 1;
for (int i = 1; i <= n; ++i) {
if (i == num * 2) {
num *= 2;
ans[i] = 1;
}
else {
ans[i] = 1 + ans[i-num];
}
}
return ans;
}
};