如何将动态规划中的滚动数组应用于长尾词问题？

本文共计371个文字，预计阅读时间需要2分钟。

滚动数组是一种优化存储空间的思想。简单来说，就是每次都使用固定的几个存储空间来达到压缩节点的目的，主要应用在递推或动态规划中（如背包问题）。

滚动数组

滚动数组是用时间换空间的一种优化思想。简单的理解就是每次都使用固定的几个存储空间达到压缩节省存储空间的作用，主要应用在递推或动态规划中（如01背包问题）。因为DP题目是一个自底向上的扩展过程，我们常常需要用到的是连续的解，前面的解往往可以舍去。所以用滚动数组优化是很有效的。利用滚动数组的话在N很大的情况下可以达到压缩存储的作用。

引子：​​LeetCode62​​

二维数组dp

class Solution {
public:
int uniquePaths(int m, int n) {
int dp[101][101] = {0};
// memset(dp, 0, sizeof(dp));
for (int i = 1; i <= m; ++i){
for (int j = 1; j <= n; ++j){
if (i == 1 || j == 1)
dp[i][j] = 1;
else
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m][n];
}
};

滚动数组写法

class Solution {
public:
int uniquePaths(int m, int n) {
int dp[101];
memset(dp, 0, sizeof(dp));
dp[1] = 1;
for (int i = 1; i <= m; ++i){
for (int j = 2; j <= n; ++j){
dp[j] += dp[j-1];
}
}
return dp[n];
}
};