Leetcode 每日一題 地下城遊戲 動态規劃（golang）

題目

分析過程

1.這道題還是要用到動态規劃，但是與之前的有些不同，如果從最大收益正向考慮時，會産生三個儲存時間，而且不是簡單的在最後加一個判斷條件，勇士在中間也必須保持正血量，是以行不通，就算實作了，時間複雜度也過高。

2.采用倒推的方法，根據題意要救出公主，從公主的位置出發，若公主目前位置為正，則勇士健康值最少為1，若為負，則需要上一步dp-目前格數值

3.用dp[i][j] 表示從坐标 (i,j) 到終點所需的最小初始值，在一般情況下，我們隻需要關注向右和向上這兩者健康點最小值

給出動态規劃方程

代碼

func calculateMinimumHP(dungeon [][]int) int {

	n := len(dungeon)
	m := len(dungeon[0])    //讀取網格數
	dp := make([][]int, n)  //建立動态存儲空間，即勇士健康點
	for i := 0; i < n; i++ {
		dp[i] = make([]int, m)
	}
	if dungeon[n-1][m-1] > 0 {
	dp[n-1][m-1] = 1//判斷最後一格即公主所在格數的上面和左邊兩格數值是否大于0，若是則勇士健康點為1
	} else {
		dp[n-1][m-1] = 1 - dungeon[n-1][m-1] //不是，則上一步dp-目前格數值
	}
	for i := n - 1; i >= 0; i-- {
		for j := m - 1; j >= 0; j-- {
			if i == n-1 && j == m-1 {
				continue      //判斷健康點是否大于0，不是則死亡
			} else if j == m-1 {
				dp[i][j]=Max(1,(dp[i+1][j]-dungeon[i][j]))
			} else if i == n-1 {
				dp[i][j]=Max(1, (dp[i][j+1]-dungeon[i][j]))
			}else {
                t1 :=Max(1,dp[i+1][j]-dungeon[i][j])
                t2 :=Max(1,dp[i][j+1]-dungeon[i][j])
				dp[i][j]=Min(t1,t2)
			}                    //兩次循環判斷一般情況，獲得最小值
		}
	}                         
	return dp[0][0]
}
func Min(x, y int) int {
    if x < y {
        return x
    }
    return y
}

func Max(x, y int) int {
    if x > y {
        return x
    }
    return y
}