格雷码:
1位:0 1
2位:(0)0 (0)1 (1)1 (1)0
3位:(0)00 (0)01 (0)11 (0)10 + (1)10 (1)11 (1)01 (1)00

后一位的直接在前一位的格雷码前+0 或者+1(+1要把数组反向),就可以生成格雷码。

用动态规划做的,内存占用有点儿大。

class GrayCode {
public:
    vector<string> getGray(int n) {
        vector<string> vec[102];
        if(n==0)return vec[0];
        vec[1].push_back("0");
        vec[1].push_back("1");
        for(int i=2;i<=n;i++){
            for(int j=0;j<vec[i-1].size();j++){
                vec[i].push_back("0"+vec[i-1][j]);
                vec[i+1].push_back("1"+vec[i-1][j]);
            }
            for(int j=0;j<vec[i-1].size();j++){
                vec[i].push_back(vec[i+1][vec[i+1].size()-1-j]);
            }vec[i+1].clear();
        }
        return vec[n];
    }
};