跳躍游戲II
相對(duì)與之前的跳躍游戲，這道題目保證能夠抵達(dá)終點(diǎn)佃迄，但是要求你輸出最短路徑。
DP三部曲梧疲，定義子問(wèn)題擦耀，定義狀態(tài)數(shù)組，和狀態(tài)轉(zhuǎn)移方程榕酒。
- 子問(wèn)題胚膊，到i個(gè)位置的最短步數(shù)故俐，等于0..i-1中能夠到i的最小步數(shù)+1
- 狀態(tài)數(shù)組: dp[i]
- 狀態(tài)轉(zhuǎn)移方程: dp[i] = min(dp[i],dp[j]+1), j =0..i
下面就是最初版的代碼
// 90 / 92 個(gè)通過(guò)測(cè)試用例
class Solution1 {
public:
int jump(vector<int>& nums) {
int dp[nums.size()];
for (int i = 0; i < nums.size(); i++) dp[i] = INT_MAX;
dp[0] = 0; //初始化第一個(gè)位置
for (int i = 1 ;i < nums.size() ; i++){
for(int j = 0; j < i ; j++){
if (nums[j] + j >= i){
dp[i] = min(dp[i],dp[j]+1);
}
}
}
return dp[nums.size()-1];
}
};
雖然代碼正確，也能得到正確的結(jié)果紊婉，但是超時(shí)了药版，卡在了一個(gè)全為1的輸入中。
優(yōu)化下代碼：外層依舊遍歷整個(gè)數(shù)組喻犁，內(nèi)層循環(huán)則是遍歷當(dāng)前數(shù)組能夠抵達(dá)的位置槽片， 更改其最小步數(shù)。
也就是狀態(tài)轉(zhuǎn)移方程變成了dp[i+j] = min(dp[i+j], dp[i]+1);
這就保證了對(duì)于全為1的數(shù)組株汉，內(nèi)層循環(huán)只會(huì)走一步筐乳，就避免了之前的情況。
class Solution2 {
public:
int jump(vector<int>& nums) {
int dp[nums.size()];
int num_len = nums.size() ;
for (int i = 0; i < nums.size(); i++) dp[i] = INT_MAX;
dp[0] = 0; //初始化第一個(gè)位置
for (int i = 0 ;i < nums.size() ; i++){
for(int j = 1; j <= nums[i] ; j++){
int next = min(i+j, num_len-1); //不能越界
dp[next] = min(dp[next],dp[i]+1);
}
}
return dp[nums.size()-1];
}
};
當(dāng)我滿懷信心運(yùn)行代碼的時(shí)候乔妈，結(jié)果還是超時(shí)了蝙云。
原來(lái)輸入中，還有一個(gè)單調(diào)遞減的情況路召，導(dǎo)致最終內(nèi)層循環(huán)次數(shù)分別為n,n-1,n-2...1位置勃刨，導(dǎo)致許多不必要的運(yùn)算。
繼續(xù)優(yōu)化：我們新增一個(gè)變量股淡，farthest身隐，表示每次能夠抵達(dá)的最遠(yuǎn)距離。如果不能保證當(dāng)前位置能夠比f(wàn)arthest走的更遠(yuǎn)的時(shí)候, 就說(shuō)明當(dāng)前位置不夠好唯灵。
同時(shí)贾铝，在內(nèi)層循環(huán)之前，我們先判斷當(dāng)前位置是否能夠直接抵達(dá)終點(diǎn)埠帕，如果可以就直接返回結(jié)果垢揩。
class Solution {
public:
int jump(vector<int>& nums) {
int num_len = nums.size() ;
if ( num_len <= 1) return 0;
int farthest = 0;
int dp[num_len];
for (int i = 0; i < num_len ; i++) dp[i] = INT_MAX - 1;
dp[0] = 0; //初始化第一個(gè)位置
for (int i = 0 ;i < num_len ; i++){
if ((i+nums[i]+1)>= num_len) return dp[i]+1;
for(int j = 1; j <= nums[i] && nums[i] + i > farthest; j++){
int next = i + j; //抵達(dá)的最后位置
dp[next] = min(dp[next],dp[i]+1);
}
farthest = i + nums[i];
}
return dp[num_len-1];
}
};
繼續(xù)優(yōu)化: 我們內(nèi)層循環(huán)每次也不是需要從當(dāng)前的下一個(gè)位置開(kāi)始更新，而是farthest-i開(kāi)始敛瓷，因?yàn)閚ext=i+j = i+farthest-i+j = farthest, 即我們從之前所能抵達(dá)最遠(yuǎn)位置開(kāi)始更新叁巨，一直更新到當(dāng)前所能抵達(dá)最遠(yuǎn)位置。
class Solution {
public:
int jump(vector<int>& nums) {
int num_len = nums.size() ;
if ( num_len <= 1) return 0;
int farthest = 0;
int dp[num_len];
for (int i = 0; i < num_len ; i++) dp[i] = INT_MAX - 1;
dp[0] = 0; //初始化第一個(gè)位置
for (int i = 0 ;i < num_len ; i++){
if ((i+nums[i]+1)>= num_len) return dp[i]+1;
for(int j = farthest - i; j <= nums[i] && nums[i] + i > farthest; j++){
int next = i + j; //抵達(dá)的最后位置
dp[next] = min(dp[next],dp[i]+1);
}
farthest = i + nums[i];
}
return dp[num_len-1];
}
};
最后的代碼提交之后運(yùn)行速度是4ms呐籽。
同樣是兩層循環(huán)锋勺，通過(guò)剪枝能夠大大提高運(yùn)算速度。
