滚动数组-动态规划之-不同路径 II_20230421网站首页 技术交流

滚动数组-动态规划之-不同路径 II_20230421

Jasonchen1224 2023-06-04 08:00:02

简介滚动数组-动态规划之-不同路径 II_20230421

DP动态规划之-滚动数组

前言

在学习不同路径II 的动态规划过程中，从介绍资料中了解到滚动数组可以进一步降低动态规划解空间的复杂度，更高效利用计算机的储存空间。动态规划中的滚动数组究竟能发挥哪些作用，在常规的动态规划中，我们又是如何进行具体的应用呢？

从本质上理解，滚动数组的作用就是为了更好利用储存空间，用有限的空间不断进行覆盖，从而完成整体算法任务，具体而言分为两类：

一维数组简化为2个或3个变量
二维数组简化为1维数组

一维数组转化为滚动数组

具体看一个斐波那契数列的例子，中规中矩的动态规划数组一般设定为dp[n+1]，其中n表示斐波那契数列的下标（位置），通过dp[n]=dp[n-1]+dp[n-2]求解出所有的斐波那契数列。

动态规划的基础解为dp[1]=1, dp[2]=1，然后通过循环求出每个位置上的斐波那契数字，最后返回dp[n]即为所求得的具体解。

int fib_normal_array(int n)
{
    int i;
    int dp[n+1];

    dp[1]=1;
    dp[2]=1;

    for(i=3;i<=n;i++)
    {
        dp[i]=dp[i-1]+dp[i-2];
    }

    return dp[n];
}

那么如何转化为滚动数组呢？通过观察我们发现，对于每个位置上的斐波那契数字，它仅仅与前面两个相邻的斐波那契数字相关，再往前的斐波那契数字与它无关。这就给我们些微的思路，尝试探索用3个单独变量来滚动实现斐波那契数字的求解。假定f1,f2和f3为连续的三个斐波那契数字，f3=f1+f2, 接下来把f2赋值给f1, f3赋值给f2，神奇的事情就会发生，让我们看具体的代码实现。

int fib_scrolling_array(int n)
{
    int i;
    int f1;
    int f2;
    int f3;

    f1=1;
    f2=1;

    for(i=3;i<=n;i++)
    {
        f3=f1+f2;
        f1=f2;
        f2=f3;
    }

    return f3;
}

用图来进一步解释说明，可以观察出，f2和f3不断滚动到f1和f2, 周而复始，最终求得f3具体值，由于新值与旧值不断交换，形象称之为滚动。
在这里插入图片描述

上述例子可以看出，通过合理的变量设定，可以把占用空间从n降低为3个变量，但是工程问题永远都有两面性，减少了储存空间，那么如果要查找，就只能找到至多三个斐波那契数字，如果设定的一维数组，那么就可以通过下标任意查询。具体采用哪种模式，需要根据具体问题具体分析。

二维数组简化为一维数组

很多情况下，动态规划问题的求解有赖于DP二维数组，通过dp[i][j]与前面已知求得的解进行关联求和或求布尔运算，从而求出dp[i][j]的具体值。

看一个具体例子，前面曾经提到的不同路径II的问题，常规情况下，利用二维DP数组进行求解，如果采用滚动数组的概念，则可以把二维数组优化为一维数组，如果进一步深入理解，也就是把二维数组的n×m个变量空间优化为m个变量空间，从形式上直观理解，二维数组自然退化为一维数组。

先给出不同路径II的问题描述，问题引用自leetcode.

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。

这个问题可以称之为条件式的动态规划问题，这源于障碍物的限制，障碍物限制会导致递归模式中的剪枝情况出现，本问题采用DP迭代动态规划，它会通过判断语句，对不同的dp[i]][j]进行赋值。

动态规划的重要特征是通过最优化子问题定义状态转移方程，可以理解为先定义最优化子问题，然后通过定义的子问题递归或迭代求出原问题的解。

对于此问题，题目要求求解最终不同路径的数目，同时限制了路径的走向，对于任意一个坐标点f(i,j)，如果需要求出到达此点的路径的总数目，可以分两种情况：

情况1，如果此处存在路障，那么f(i,j)=0, 用编程语言描述，如果路障数组在某处obstacleGrid[i][j]的值为1，那么这个点和之前任何点都没有关系，到达此处的路径总数为0
情况2，如果此处畅通无阻，这是可以把(i,j)看作是路径的终点，显而易见，f(i,j)和它相邻的做单元格和上单元格相关，进一步观察，实际上f(i,j)的路径总数取决于f(i-1,j) 和f(i,j-1)的数量之和，我们可以称作f(i-1,j)和f(i,j-1)为f(i,j)的子问题

从上面分析可以看出，采用动态规划最简单的方法就是定义一套二维数组，数组的坐标位置代表机器人所需要到达的目标位置，数组的值来储存到达此处的不同路径总数目。

对于DP值，需要找到它的基础值，也就是DAG路径当中的终点值。

在这里插入图片描述

对于第一行或第一列的障碍物数组，只要碰到出现障碍物，那么障碍物之后的不同路径总数目都为0，具体看实际例子，比如obstacle_grid[0][2]=1,那么它(包括本身）之后的在第一行中的DP数组的值(路径数目)都为0。同理对于obstacle_gride[0][3]的值为1（障碍物），那么它（包括本身）之后的所有第一列当中的DP数组的值均为0.
在这里插入图片描述

int unique_path(int **obstacle_grid, int row, int col)
{
    int i; //row index
    int j; //column index
    int dp[row][col];

    memset(dp,0,sizeof(dp));

    dp[0][0]=(obstacle_grid[0][0]==0);

    for(i=1;i<row;i++)
    {
        dp[i][0]=dp[i-1][0] && !(obstacle_grid[i][0]);
    }

    for(j=1;j<col;j++)
    {
        dp[0][j]=dp[0][j-1] && !(obstacle_grid[0][j]);
    }

    for(i=1;i<row;i++)
    {
        for(j=1;j<col;j++)
        {
            if(obstacle_grid[i][j]==0)
            {
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
            else
            {
                dp[i][j]=0; //depends on the current node isntead of previous node
            }            
        }
    }

    return dp[row-1][col-1];
}

void create_obstacle(int ***obstacle_grid, int row, int col)
{
    int i;
    int j;

    *obstacle_grid=(int **)malloc(sizeof(int *)*row);

    for(i=0;i<row;i++)
    {
        *(*obstacle_grid+i)=(int *)malloc(sizeof(int)*col);
        memset(*(*obstacle_grid + i),0,sizeof(int)*col);
    }
    //(*obstacle_grid)[1][1]=1
    return;
}
#endif

大家如果仔细观察,可以发现，如果当前位置上没有路障，那么DP储存的不同路径数目仅和其紧邻左侧和上侧值有关，这时候最朴素的理解是不是可以采用dp[m][2]来储存数据呢？答案当然是可行的，用两行一维数组来储存，并且交替更新数据，可以得到所求的结果，没有任何问题。

再进一步深度思考，能否采用一维数组实现算法呢？答案也是肯定的，只不过需要用图示来说明一下它的实际来历。假定要计算新的DP[3]值，那么如何从同一行中的数值进行计算呢，实际上很简单DP[3]=DP[3](原有的值，相当于上侧)+DP[2](原有的值，相当于左侧)，通过在同一行数组中的“滚动”更新，从而求得答案。
在这里插入图片描述

具体代码实现：

int unique_path(int **obstacle_grid, int row, int col)
{
    //using the scrolling array/list
    int dp[col];
    int i;
    int j;
    memset(dp,0,sizeof(dp)); //need set the initial value as zero

    dp[0]=(obstacle_grid[0][0]==0);

    for(i=0;i<row;i++)
    {
        for(j=0;j<col;j++)
        {
            if(obstacle_grid[i][j]==1)
            {
                dp[j]=0;
            }
            else if((j-1)>=0 && obstacle_grid[i][j]==0)
            {
                dp[j]=dp[j]+dp[j-1];
            }
        }
    }

    return dp[col-1];
}