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_比特位计数_简单动态规划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。