dp中的滚动数组
发布时间：2023-10-18 00:17:57 139 相关标签：
滚动数组
滚动数组是用时间换空间的一种优化思想。简单的理解就是每次都使用固定的几个存储空间达到压缩节省存储空间的作用，主要应用在递推或动态规划中（如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];
}
};
文章来源： https://blog.51cto.com/u_13875041/5877845
特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。
举报
