leetcode 338. Counting Bits (记数位)

题目要求

给定非负整数num。 对于0≤i≤num范围内的每个数字i，计算其二进制表示中的1的数量并将它们作为数组返回。如下图

解题思路

规律不太好找，我们先写出几个表达式

Index : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 num : 0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4

根据Num关系，我们可以得到如下的几个关系式： 实际上，我们发现dp[2] = 1, dp[4] = 1, dp[8] = 1, 而其他的式子都是由这几个推导出来的，符合我们动态规划的特点。 得到

dp[index] = dp[index-offset]

当offset=2，4，8即2的倍数时，我们发现，index=offset。这样我们就可以写代码啦。

主要代码c++

class Solution { public: vector<int> countBits(int num) { vector<int>res(num+1,0); int offset = 1; for(int i=1; i<=num; ++i) { if(2*offset == i) offset = 2 * offset; res[i] = res[i-offset] + 1; } return res; } };