338. Counting Bits_比特位计数_简单动态规划

https://leetcode.com/problems/counting-bits/

这是初步了解动态规划后做的第一道题，体验还不错。。。

看完题目要求后，写出前10个数的二进制数，发现了以下规律：

• 2的幂的二进制数中只有一个1
• 若n不是2的幂，可以拆分为两个数的和（a+b），a为比n小的最接近的2的幂

拆分后，res[n] = res[a] + res[b]

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

 

转载于:https://www.cnblogs.com/tornado549/p/10423811.html

总结

以上是生活随笔为你收集整理的338. Counting Bits_比特位计数_简单动态规划的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。