肯定是用DP，但我自己想了一个奇怪的方法，勉强过了…
使用dp[i] = {steps}，表示可以达到stones[i]的最后一跳的unit的集合。
dp[0] = {0}
dp[1] = {1} if stones[1] = 1 else {}
然后对于stones[i]，枚举所有step – 1, step, step + 1三种情况，看看是否可以跳到新的石头上面（使用一个hashtable判断），如果可以的吧，把跳的unit存到dp[j]中。相当于推了。
需要使用hashset去重，不然会超时。
时间复杂度：O(n2)
空间复杂度：O(n2)
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
class Solution { public: bool canCross(vector<int>& stones) { if (stones[1] != 1) return false; unordered_map<int, int> m; const int n = stones.size(); for (int i = 0; i < n; ++i) m[stones[i]] = i; // dp[i] = {steps} steps to jump to stone[i]. vector<unordered_set<int>> dp(n); dp[0] = {0}; dp[1] = {1}; for (int i = 2; i < n; ++i) { for (int last : dp[i - 1]) { for (int cur = last - 1; cur <= last + 1; cur++) { if (cur < 1) continue; const int t = stones[i - 1] + cur; auto it = m.find(t); if (it != end(m)) dp[it->second].insert(cur); } } } return !dp.back().empty(); } }; |
“优化”：由于每次只能k-1,k,k+1steps，所以最大的units和n是线性关系，达到stones[i]最多跳i+1个units。
可以用二维数组dp[j][k] := 是否可以通过k步跳到stones[j].
dp[j][k] = dp[i][k-1] || dp[i][k] || dp[i][k+1], k = stones[j] – stones[i]. 即从stones[i]跳到stones[j]，并且要求跳到stones[i]的可能步数中存在k-1,k,k+1。
时间复杂度和空间复杂度是一样的。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Solution { public: bool canCross(vector<int>& stones) { const int n = stones.size(); vector<vector<bool>> dp(n, vector<bool>(n + 1)); dp[0][0] = true; for (int i = 1; i < n; ++i) for (int j = 0; j < i; ++j) { const int d = stones[i] - stones[j]; if (d >= n) continue; // undefined range. dp[i][d] = dp[i][d] || (dp[j][d - 1] || dp[j][d] || dp[j][d + 1]); } return any_of(begin(dp.back()), end(dp.back()), [](bool x) { return x; }); } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment