龙与地下城游戏问题

典型的动态规划

从左上角触发，每次向右或向下走，最后到达右下角，我们要求的是初始值的血
dp[i][j] 从arr[i][j] 位置到右下角最少需要多少血
dp[m-1][n-1] = arr[m-1][n-1] > 0 ? 1:-arr[m-1][n-1] +1
//能到达的下一个位置 -去当前位置的值，如果为-标示要加血，如果为正标示要减学
dp[m-1][j] = max( dp[m-1][j+1] -arr[m-1][j],1 )
dp[i][n-1] = max( dp[i+1][n-1] - arr[i][n-1] ,1)
dp[i][j] = min( max(dp[i][j+1] - arr[i][j],1),max(dp[i+1][j] - arr[i][j],1) )

至于空间压缩

压缩空间，首先基于经典解法，一般压缩掉外循环的维度，内循环 通过 更新前，更新后，或者调整更新顺序替代 为需要的元素

代码

package main
import (
    "fmt"
)
func main(){
    var n,m int
    fmt.Scanln(&n,&m)
    arr := make([][]int,n)
    for i:=0;i<n;i++{
        arr[i] = make([]int,m)
        for j:=0;j<m;j++{
            fmt.Scanf("%d",&arr[i][j])
        }
    }
    helper2(arr,n,m)
    return
}
func helper2(arr [][]int,n,m int){
    dp := make([]int,n)
    dp[m-1] = 1
    if arr[n-1][m-1] < 0{
        dp[m-1] = -arr[n-1][m-1]+1
    }
    for j:=m-2;j>=0;j--{
        dp[j] = max(dp[j+1] - arr[n-1][j],1)
    }
    for i:=n-2;i>=0;i--{
        dp[m-1] = max(dp[m-1] - arr[i][m-1],1)
        for j:=m-2;j>=0;j--{
            //dp[j+1] 等同于 dp[i][j+1] dp[j] 等同于 dp[i+1][j] 因为dp[j] 在更新之前
            right := max(dp[j+1] - arr[i][j],1)
            down := max(dp[j] - arr[i][j],1)
            dp[j] = min(right,down)
            //pre = dp[j]
        }
    }
    fmt.Println(dp[0])
    return 
}
func helper(arr [][]int,n,m int){
    dp := make([][]int,n)
    for i:=0;i<n;i++{
        dp[i] = make([]int,m)
    }
    dp[n-1][m-1] = 1
    if arr[n-1][m-1] < 0{
        dp[n-1][m-1] = -arr[n-1][m-1]+1
    }
    /*for i:=n-2;i>=0;i--{
        dp[i][m-1] = max(dp[i+1][m-1] - arr[i][m-1],1)
    }*/
    for j:=m-2;j>=0;j--{
        dp[n-1][j] = max(dp[n-1][j+1] - arr[n-1][j],1)
    }
    for i:=n-2;i>=0;i--{
         dp[i][m-1] = max(dp[i+1][m-1] - arr[i][m-1],1)
        for j:=m-2;j>=0;j--{
            right := max(dp[i][j+1] - arr[i][j],1)
            down := max(dp[i+1][j] - arr[i][j],1)
            dp[i][j] = min(right,down)
        }
    }
    fmt.Println(dp[0][0])
    return 
}
func min(a,b int) int {
    if a < b {
        return a
    }
    return b
}
func max(a,b int) int {
    if a < b {
        return b
    }
    return a 
}