本專欄內(nèi)容為：算法學(xué)習(xí)專欄，分為優(yōu)選算法專欄，貪心算法專欄，動(dòng)態(tài)規(guī)劃專欄以及遞歸，搜索與回溯算法專欄四部分。 通過(guò)本專欄的深入學(xué)習(xí)，你可以了解并掌握算法。
??博主csdn個(gè)人主頁(yè)：小小unicorn
?專欄分類：動(dòng)態(tài)規(guī)劃專欄
??代碼倉(cāng)庫(kù)：小小unicorn的代碼倉(cāng)庫(kù)??
??????關(guān)注我?guī)銓W(xué)習(xí)編程知識(shí)
題目來(lái)源
本題來(lái)源為：
Leetcode 174. 地下城游戲
題目描述
惡魔們抓住了公主并將她關(guān)在了地下城 dungeon 的 右下角 。地下城是由 m x n 個(gè)房間組成的二維網(wǎng)格。我們英勇的騎士最初被安置在 左上角 的房間里，他必須穿過(guò)地下城并通過(guò)對(duì)抗惡魔來(lái)拯救公主。
騎士的初始健康點(diǎn)數(shù)為一個(gè)正整數(shù)。如果他的健康點(diǎn)數(shù)在某一時(shí)刻降至 0 或以下，他會(huì)立即死亡。
有些房間由惡魔守衛(wèi)，因此騎士在進(jìn)入這些房間時(shí)會(huì)失去健康點(diǎn)數(shù)（若房間里的值為負(fù)整數(shù)，則表示騎士將損失健康點(diǎn)數(shù)）；其他房間要么是空的（房間里的值為 0），要么包含增加騎士健康點(diǎn)數(shù)的魔法球（若房間里的值為正整數(shù)，則表示騎士將增加健康點(diǎn)數(shù)）。
為了盡快解救公主，騎士決定每次只 向右 或 向下 移動(dòng)一步。
返回確保騎士能夠拯救到公主所需的最低初始健康點(diǎn)數(shù)。
算法原理
1.狀態(tài)表示
經(jīng)驗(yàn)+題目要求
對(duì)于本題而言就是：
dp[i][j]表示：從[i,j]位置的出發(fā)，到達(dá)終點(diǎn)，所需要的最低初始健康點(diǎn)數(shù)
2.狀態(tài)轉(zhuǎn)移方程
分兩種情況：
因此狀態(tài)方程為：
為什么最后還要和1取Max呢？這是為了防止最后結(jié)果是個(gè)負(fù)數(shù)
dp[i][j]=min(dp[i+1][j],dp[i][j+1])-d[i][j];
dp[i][j]=max(1,dp[i][j]);
3.初始化
看圖分析很容易就知道應(yīng)該如何初始化。
4.填表順序
從下往上填每一行，每一行從右往左
5.返回值
dp[0][0]
代碼實(shí)現(xiàn)
動(dòng)態(tài)規(guī)劃的代碼基本就是固定的四步：
1.創(chuàng)建dp表
2.初始化
3.填表
4.返回值
本題完整代碼實(shí)現(xiàn)：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-837143.html
class Solution
{
public:
int calculateMinimumHP(vector<vector<int>>& d)
{
int m=d.size(),n=d[0].size();
//創(chuàng)建dp表
vector<vector<int>> dp(m+1,vector<int>(n+1,INT_MAX));
//初始化
dp[m][n-1]=dp[m-1][n]=1;
//填表
for(int i=m-1;i>=0;i--)
{
for(int j=n-1;j>=0;j--)
{
//狀態(tài)轉(zhuǎn)移方程
dp[i][j]=min(dp[i+1][j],dp[i][j+1])-d[i][j];
dp[i][j]=max(1,dp[i][j]);
}
}
return dp[0][0];
}
};
時(shí)間復(fù)雜度：O(MxN)
空間復(fù)雜度：O(MxN)文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-837143.html
到了這里，關(guān)于【動(dòng)態(tài)規(guī)劃專欄】專題二：路徑問(wèn)題--------6.地下城游戲的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
