久久精品中文字幕av,av.涩涩涩涩涩涩涩涩,亚洲国产日韩欧美精品成人久久久,成人福利电影免费在线观看,日产国产原创av,日韩av午夜激情,bt天堂中文字幕,超级碰人妻在线视频,欧美老熟妇久久一区二区

# Jump Game ### Source - lintcode: [(116) Jump Game](http://www.lintcode.com/en/problem/jump-game/) ~~~ Given an array of non-negative integers, you are initially positioned at the first index of the array. Each element in the array represents your maximum jump length at that position. Determine if you are able to reach the last index. Example A = [2,3,1,1,4], return true. A = [3,2,1,0,4], return false. ~~~ ### 題解(自頂向下-動(dòng)態(tài)規(guī)劃) 1. State: f[i] 從起點(diǎn)出發(fā)能否達(dá)到i 1. Function: `f[i] = OR (f[j], j < i ~\&\&~ j + A[j] \geq i)`, 狀態(tài) jjj 轉(zhuǎn)移到 iii, 所有小于i的下標(biāo)j的元素中是否存在能從j跳轉(zhuǎn)到i得 1. Initialization: f[0] = true; 1. Answer: 遞推到第 N - 1 個(gè)元素時(shí)，f[N-1] 這種自頂向下的方法需要使用額外的 O(n)O(n)O(n) 空間，保存小于N-1時(shí)的狀態(tài)。且時(shí)間復(fù)雜度在惡劣情況下有可能變?yōu)?1+2+?+n=O(n2)1 + 2 + \cdots + n = O(n^2)1+2+?+n=O(n2), 出現(xiàn) [TLE](# "Time Limit Exceeded 的簡(jiǎn)稱(chēng)。你的程序在 OJ 上的運(yùn)行時(shí)間太長(zhǎng)了，超過(guò)了對(duì)應(yīng)題目的時(shí)間限制。") 無(wú)法AC的情況，不過(guò)工作面試能給出這種動(dòng)規(guī)的實(shí)現(xiàn)就挺好的了。 ### C++ from top to bottom ~~~ class Solution { public: /** * @param A: A list of integers * @return: The boolean answer */ bool canJump(vector<int> A) { if (A.empty()) { return true; } vector<bool> jumpto(A.size(), false); jumpto[0] = true; for (int i = 1; i != A.size(); ++i) { for (int j = i - 1; j >= 0; --j) { if (jumpto[j] && (j + A[j] >= i)) { jumpto[i] = true; break; } } } return jumpto[A.size() - 1]; } }; ~~~ ### 題解(自底向上-貪心法) 題意為問(wèn)是否能從起始位置到達(dá)最終位置，我們首先分析到達(dá)最終位置的條件，從坐標(biāo)i出發(fā)所能到達(dá)最遠(yuǎn)的位置為 f[i]=i+A[i]f[i] = i + A[i]f[i]=i+A[i]，如果要到達(dá)最終位置，即存在某個(gè) iii 使得f[i]≥N?1f[i] \geq N - 1f[i]≥N?1, 而想到達(dá) iii, 則又需存在某個(gè) jjj 使得 f[j]≥i?1f[j] \geq i - 1f[j]≥i?1. 依此類(lèi)推直到下標(biāo)為0. **以下分析形式雖為動(dòng)態(tài)規(guī)劃，實(shí)則貪心法！** 1. State: f[i] 從 iii 出發(fā)能否到達(dá)最終位置 1. Function: f[j]=j+A[j]≥if[j] = j + A[j] \geq if[j]=j+A[j]≥i, 狀態(tài) jjj 轉(zhuǎn)移到 iii, 置為`true` 1. Initialization: 第一個(gè)為`true`的元素為 `A.size() - 1` 1. Answer: 遞推到第 0 個(gè)元素時(shí)，若其值為`true`返回`true` ### C++ greedy, from bottom to top ~~~ class Solution { public: /** * @param A: A list of integers * @return: The boolean answer */ bool canJump(vector<int> A) { if (A.empty()) { return true; } int index_true = A.size() - 1; for (int i = A.size() - 1; i >= 0; --i) { if (i + A[i] >= index_true) { index_true = i; } } return 0 == index_true ? true : false; } }; ~~~ ### 題解(自頂向下-貪心法) 針對(duì)上述自頂向下可能出現(xiàn)時(shí)間復(fù)雜度過(guò)高的情況，下面使用貪心思想對(duì)i進(jìn)行遞推，每次遍歷A中的一個(gè)元素時(shí)更新最遠(yuǎn)可能到達(dá)的元素，最后判斷最遠(yuǎn)可能到達(dá)的元素是否大于 `A.size() - 1` ### C++ greedy, from top to bottom ~~~ class Solution { public: /** * @param A: A list of integers * @return: The boolean answer */ bool canJump(vector<int> A) { if (A.empty()) { return true; } int farthest = A[0]; for (int i = 1; i != A.size(); ++i) { if ((i <= farthest) && (i + A[i] > farthest)) { farthest = i + A[i]; } } return farthest >= A.size() - 1; } }; ~~~