写在前面
之前刷动态规划的题目，多需要用到二维数组（也许后面再优化成一维）。如果每次都按照给定数的范围直接声明为全局二维数组变量，又总觉得的不够优雅。查阅了一些网上的资料后，总结了一些使用方法，就写下这篇博文用以记录。
方法1——动态分配（new）一维数组，再强制类型转换为二维（个人使用，推荐指数：⭐⭐⭐⭐）
直接看例子
/** 假设需要根据两个string的长度建立二维数组 */
const int sz1 = str1.size();
const int sz2 = str2.size();
/** 动态分配内存 */
auto f = new int[sz1 * sz2];
auto dp = (int (*)[sz2])f;
/** 这里放置自己制造bug的操作*/
// abaabaaba， 直接dp[i][j]使用即可
/** 制造完了别忘记释放栈空间 */
delete[] f;
f = nullptr;
dp = nullptr;
注意，auto dp = (int (*)[sz2]f这条语句，sz2的大小一定要是后面使用二维数组时最低维的大小。
如果按照上面的类型转换方式，下面这样写会出现bug（注意sz1和sz2的顺序）：
for (int i = 0; i < sz2; ++i)
for (int j = 0; j < sz1; ++j)
// do something;
/** 其实大概率你啥也do不了，程序跑飞了 */
这个方法优点和缺点都很明显，灵活且完全和使用全局二维数组方法一样，且释放内存简单，但是使用存在危险性。如果觉得自己把握不住，建议先考虑其他方法。
另外，请读者考虑一下，可以使用如下的二重指针代替一维数组的指针进行类型转换吗？
auto f = new int[sz1 * sz2];
auto dp = (int **)f; /** 二重指针真的可以吗？*/
若觉得可行的话，可能对二维数组和二重指针的理解出现了偏差。试想，我们按照dp存储的地址值a去寻址，得到地址a中存储的值b，再按照值b去寻址的话会发生什么？（本例中，b的值的根本不是地址，而是数组的值！）
我们思考后也不难理解，为什么声明二维数组的形参类型或者是强制类型转换时，一定要正确指定最低维的大小。
方法2——分配一维数组，以二维数组的方式使用（推荐指数：⭐⭐⭐）
其实如果不是非要追求“传统”的使用二维数组的方式，也可以不用强制类型转换的方法。
只需要把握一点：二维数组的所有元素，在内存中是连续排列的。
那么我们可以按照如下的方式使用分配的二维数组：
/** 假设需要根据两个string的长度建立二维数组 */
const int sz1 = str1.size();
const int sz2 = str2.size();
/** 动态分配内存 */
auto f = new int[sz1 * sz2];
/** 给每个元素赋值 */
for (int i = 0, idx = 1; i < sz1; ++i)
for (int j = 0; j < sz2; ++j, ++idx)
f[i * sz2 + j] = idx; /** 相当于 arr[i][j] = idx; */
/** 别忘记释放栈空间 */
delete[] f;
f = nullptr;
与方法一大同小异，因此注意事项也一样，注意f[i * sz2 + j]中sz2是最低维的大小。
方法3——多次动态分配（也需要多次释放）（推荐指数：⭐⭐）
简单说，就是动态分配一维数组，然后把这些数组的指针存储到一个数组元素为一维数组的数组中。
代码如下：
/** 假设需要根据两个string的长度建立二维数组 */
const int sz1 = str1.size();
const int sz2 = str2.size();
/** 分配一个数组元素为一维数组的数组 */
auto dp = new int *[sz1];
/** 给数组每个元素赋值 */
for (int i = 0; i < sz1; ++i)
dp[i] = new int[sz2];
/** 这里放置自己制造bug的操作*/
// abaabaaba
/** 制造完了别忘记释放栈空间 */
for (int i = 0; i < sz1; ++i)
delete[] dp[i];
delete[] dp;
注意最后要先释放元素的内存。
（小声说，应该很少有人用这种方法？）
方法4——使用vector(推荐指数：⭐⭐⭐⭐⭐)
前面的几种方法多少是不太 idiomatic C++，最后当然要请出我们的STL。
没什么说的，直接看代码：
vector<vector<int> > dp(str1.length(), vector<int>(str2.length(), 0));
优点是不用再担心内存释放的问题，并且vector有很多方便的成员函数可以使用。
另外，在刷题的时候如果要判断二维vector是否为空，可以使用如下语句：
if (dp.empty() || dp[0].empty())
return ;
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
