逆向动态规划（DP）：小蚂蚁遗迹探秘

shaowu459

shaowu459

这个问题无法用之前说过的基础最小路径和动态规划方法解决。如果定义dp[j]代表从起点活着通过(i,j)需要的最少体力值，只看下面两行数据的话最优解是初始带2点体力值：


但是，如果加上一行：

最优解并非从第二行最右下角的0过来，因为这样初始需要5个体力值，而下面路径只需要3个初始体力值：

也就是说，如果按之前的方法，最右下角的最优解应该取左侧和上方的最小值，但是取到的最小值却不是到当前位置的最优解。

shaowu459

这种情况下，可以逆向，从最右下角开始考虑。设走出最右下角后最小值体力剩1，然后往回走，向左和向上，直到走的左上角。
设置dp[j]代表：保证从(i,j)出发能活着到达宝藏时，到达（i，j）时需要的最少体力值。dp[0][0]是最终要求解问题，dp[10-1][10-1]是最简单问题。


举例说明：
1）最右下角是-18，那么要保证出去后剩1个体力值，所以到达右下角的时候体力值最少应该是19（1减去-18）。也就原来减少体力的往回加，原来加体力的减掉。
2）最后一行再往左走，单元格值是7，如果从这里到右侧的18需要最小19个体力值，所以到7这个单元格时最小体力值可以是12（19-7）。
3）从最右下角的-18往上走，单元格值是-19，为了保证到右下角能有19个体力值，所以到达-19这个单元格的最小体力值要是38（19减去-19）。
4）以此类推，但是如果通过计算得到的数字是负数，则要保留1，保证最少带着一个体力值过来。

shaowu459

公示实现就比较简单了，和之前的二维转一维用法一致，只不过从最后一个元素往前遍历：
=@REDUCE(
    1,       在宝藏处最小体力值1
    ROW(1:100),   循环100次
    LAMBDA(x, y,
        LET(
            s, INDEX(x, 10),   提取x里第10个元素，也就是当前值的上方元素
            VSTACK(
                MAX(
                    1,   和1取最大值，保证至少带着一个体力值过来，也就是得活着过来
                    IFS(
                        y < 11,   如果在第一行
                        @x,    取x第一个元素，也即当前值左侧
                        MOD(y, 10) = 1,   如果是第一列
                        s,   保留x第10个元素，业绩当前值上方元素
                        1,  其他情况
                        MIN(s, @x)    取两者较小者
                    ) - INDEX(TOCOL(A2#), 101 - y)  减去从最后一个往前逐个取的值
                ),
                x
            )
        )
    )
)

捡回一个小僵尸

超人老师还可以附上B站的视频呀

shaowu459

捡回一个小僵尸 发表于 2024-10-15 11:37
超人老师还可以附上B站的视频呀

这个比双路dp那个简单的多，就不附了