格雷码

这道题目可以用普通的循环来做，也可以用动态规划来做，相比起来动态规划的思路更加清晰，代码逻辑更加紧密。

当n为1时，输出0,1，n为2时，输出00,01,11,10，当n为3时，输出00,01,11,10,110,111,101,100。

规律：11,10是在1,0高位上+1得到；110,111,101,100是在10,11,01,00高位上+1得到，代码如下：

//
// Created by jt on 2020/8/25.
//
class Solution {
public:
    /**
     *
     * @param n int整型
     * @return int整型vector
     */
    vector<int> grayCode(int n) {
        // write code here
        vector<int> res(1, 0);
        for (int i = 0; i < n; ++i) {
            int topBit = 1 << i;
            for (int j = res.size() - 1; j >= 0; --j) {
                res.push_back(topBit | res[j]);
            }
        }
        return res;
    }
};