338 题 PHP DP 方法解法

 /**
     * DP 方程
     * F(0) = 0 , N = 0
     * F(N) = F(N/2) + N%2 , N > 0
     */
    function countBits($num)
    {
        $res[] = 0;
        for ($i = 1; $i <= $num; $i++) {
            $res[$i] = $res[(int)$i / 2] + $i % 2;
        }
        return $res;
    }

338题 PHP 的解法：

function countBits($num) {
       $res = [$num+1=>0];
       for($i=1;$i<=$num;$i++) {
           $res[$i] +=$res[$i&($i-1)] +1;
       }
       return $res;
    }
声明一下，本地 环境每次会有 Notice 的错误提示，也有出现结果不同的时候。但是可以通过 leetcode 的题。

338题，C++，动态规划思想，打败99%：
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> result = { 0 };
        int highLevelNum;

        for (int i = 1; i <= num; i++)
        {
            if (result[i - 1] & 1 == 0)
            {
                result.push_back(result[i - 1] + 1);
            }
            else
            {
                //从右到左，首个0往右的低位1过滤掉，留下highLevelNum
                highLevelNum = i - 1 & i;
                //若highLevelNum是0，即i-1==(2^n)-1，则由于进位result[i]=1
                //若highLevelNum非0，则结果是highLevelNum中1的个数+1，hightLevelNum小于i，其result已知
                result.push_back(highLevelNum == 0 ? 1 : result[highLevelNum] + 1);
            }
        }

        return result;
    }
};

338.php版 动态规划。
递推公式，自己找个例子[0,1,1,2,1,2,2,3, 1,2, 2, 3, 2, 3, 3, 4]，然后找找规律
    function countBits($num) {
        // 使用动态规划
        $dp[0] = 0;
        if(empty($num)) {
            return $dp;
        }
        $dp[1] = 1;
        for($i = 2; $i <= $num; $i++) {
            // $a = $a / 2 + $a % 2;
            $dp[$i] = $dp[$i / 2] + $dp[$i % 2];
        }
        return $dp;
    }

231 题两种 PHP 解法:

A:
// 循环的笨办法
function isPowerOfTwo($n)
{
    if ($n == 1) return true;
    if ($n == 0) return false;
    if ($n / 2 === 0) {
        return true;
    } else {
        if ($n / 2 > 0) {
            if (isPowerOfTwo($n / 2) == true) {
                return true;
            }
        }
        return false;
    }
}
B:
// 位运算的方法。
function isPowerOfTwo1($n)
{
    return $n > 0 && ($n & ($n - 1)) == 0;
}

还有一种比较容易顺着思考的，就是干掉最高位的1，
好比两个power_2之间的 是符合递推的，如2和4之间只有一个3，4和8之间有5，6，7
3=2+1
5=4+1
6=4+2
7=4+3

因为1，2，3已经在前面计算过了，所以bits_cnt[7]=bits_cnt[4]+bits_cnt[3] 这样。