2021年第一天，学习lua源代码，本文记录学习过程中遇到的问题和知识点，希望能在2021年上半年完成lua源代码的初步学习。

使用C模拟面向对象

使用union将所有数据包起来，一般情况下，如果看到一个数据类型是union，就可以知道这个数据想以一种较为省内存的方式来表示多种用途，而这些用途之间是互斥的，也就是说，在某个时刻该数据类型只会是其中的一个含义，一个简单的例子：

#include <stdio.h>
#include <stdlib.h>
typedef struct string {
    int len;
    char *data[0];
}string;

typedef struct number {
    double num;
}number;

typedef struct value {
    int type;
    union {
        string str;
        number num;
    }value;
}value;

int main()
{
    string *str = (string *)malloc(sizeof(string) + sizeof(char) * 1024);
    str->len = 1024;

    value val;
    val.type = 1;
    val.value.str = *str;

    free(str);
    return 0;
}

递归算法优化(空间换时间)

看lua源码发现对性能要求做到了极致，能用char解决的不会用int，看另一本书上从递归讲到动态规划时举的一个例子非常好。在leetcode上找到一个题目，可以进行代码编写验证leetcode-70,题目非常简单，我们很快写出了答案：

class Solution {
public:
    int climbStairs(int n) {
        if(n == 1 || n == 2)
            return n;
        
        return climbStairs(n - 1) + climbStairs(n - 2);
    }
};

可是却在计算45时报错，原因是我们重复计算了太多，例如f(6)= f(5) + f(4),计算f(5)=f(4)+f(3)，这里可以看到重复计算了f(4),当计算45时存在大量的重复计算，导致超时，一种空间换时间的方法是在计算时缓存已经得到的结果，这样就不会重复计算：

class Solution {
private:
    int climbStairs_helper(int n,vector<int> &res)
    {
       if (n == 1 || n ==2)
            res[n] = n;
        else if (res[n] == 0)
            res[n] = climbStairs_helper(n-1,res) + climbStairs_helper(n-2,res);

        return res[n];
    }
public:
    int climbStairs(int n) {
        vector<int> res(n + 1,0);
        climbStairs_helper(n,res);
        return res[n];
    }
};

这个问题最好的解法是使用动态规划DP，从递归到递归加记忆化，这个过程体现了空间换时间，进而更自然的可以使用从底向上递推，引出动态规划算法，这里不再赘述。