Question:
跳河问题。给一个0/1数组R代表一条河,0代表水,1代表石头。起始位置R[0]等于1,
初速度为1. 每一步可以选择以当前速度移动,或者当前速度加1再移动。只能停留在石
头上。问最少几步可以跳完整条河流。
给定数组为R=[1,1,1,0,1,1,0,0],最少3步能过河:
第一步先提速到2,再跳到R[2];
第二步先提速到3,再跳到R[5];
第三步保持速度3,跳出数组范围,成功过河。
题目来自: http://www.mitbbs.com/article_t1/JobHunting/32617501_0_1.html
Solution 1:
int FlogCrossRiver(string river) { if (river.empty()) { return 0; } vector<vector<pair<size_t, int>>> vp(river.size()); vp[0].emplace_back(1, 1); int res = INT_MAX; for (size_t i = 0; i < vp.size(); ++i) { if (river[i] == '0') { continue; } for (auto pr : vp[i]) { if (i + pr.first >= vp.size()) { res = min(pr.second, res); } else if (river[i + pr.first] == '1') { vp[i + pr.first].emplace_back(pr.first, pr.second + 1); } if (i + pr.first + 1 >= vp.size()) { res = min(pr.second, res); } else if (river[i + pr.first + 1] == '1') { vp[i + pr.first + 1].emplace_back(pr.first + 1, pr.second + 1); } } } return res; } void FlogCrossRiverTest() { cout << "11101100t" << FlogCrossRiver("11101100") << endl; cout << "11111111t" << FlogCrossRiver("11111111") << endl; cout << "11101000t" << FlogCrossRiver("11101000") << endl; cout << "11010101t" << FlogCrossRiver("11010101") << endl; }
Solution2:
DP状态方程:f(i,j) = min( f(i-j, j), f(i-j, j-1) ) + 1
i: 当前石头在数组中所处的index (0 based)
j: 到达i时的可能最大步数, <= sqrt(i*2) 假设处处有石子,那么青蛙可以随意跳跃,每次跳跃步伐比前一次跳跃大1,就有1+2+..+j = j(j+1)/2 = i, j^2+j = i*2, 所以 j <= sqrt(i*2)
f(i, j): 以步数j到达i时所需的最少跳跃次数,其中f(0,1)=0
时间和空间复杂度均为O(n^(3/2))
public int minFrogJumps(int[] a) { int len = a.length; int[][] f = new int[len][(int)Math.sqrt(len * 2) + 1]; int ans = Integer.MAX_VALUE; for (int i = 1; i < len; i++) { Arrays.fill(f[i], -1); if (a[i] == 0) { continue; } for (int j = 1; j <= (int)Math.sqrt(i * 2); j++) { if (a[i - j] == 0) { f[i][j] = -1; continue; } if (f[i - j][j] == -1 && f[i - j][j - 1] == -1) { continue; } if (f[i - j][j] != -1) f[i][j] = f[i - j][j] + 1; if (j > 1 && f[i - j][j - 1] != -1) { if (f[i][j] == -1) f[i][j] = f[i - j][j - 1] + 1; else f[i][j] = Math.min(f[i - j][j - 1] + 1, f[i][j]); } if (i + j + 1 >= len) { ans = Math.min(f[i][j] + 1, ans); } } } return ans; }
相关推荐
带跳多值随机微分方程不变测度的存在性、唯一性,关岳,巫静,本文主要研究L'evy驱动的多值随机微分方程解过程的指数遍历性问题。通过$L^2$-收敛结果,结合Girsanov变换、耦合方法和停止理论,对方程的
matlab频谱分析代码用于变更检测和时间序列分析的软件包 ...Jumps Upon Spectrum and Trend (JUST) JUSTdecompose - JUST Decomposition into Trend, Seasonal, and Remainder Components JUSTmonito
Asymptotic behavior of neutral delay differential equation of euler form with constant impulsive jumps
Backward Doubly Stochastic Differential Equations with Jumps and Stochastic Partial Differential-Integral Equations,朱庆峰,石玉峰,A type of backward doubly stochastic differential equations driven ...
Special attention is paid to Poisson random measures and their roles in regulating the excursions of Brownian motion and the jumps of Levy and Markov processes. Each chapter has a large number of ...
传送门 题意: 开始位置在0,问能否跳到n+1位置 每步只能跳d 在1——n每个位置有方向,L,R,求d的最小值 思路: 只用找相邻两个R之间的最大值即可 代码: #include #include ...typedef long long l
Forward-backward doubly stochastic differential equations with random jumps and stochastic partial differential-integral equations,朱庆峰,石玉峰,A type of forward-backward doubly stochastic ...
- Ported most of Qemu's 'virtual VFAT' block driver (except runtime write support, but plus FAT32 suppport) - Added write protect option for floppy drives. - Bugfixes / improved internal debugger + ...
K-SVD通过构建字典来对数据进行稀疏表示,经常用于图像压缩、编码、分类等应用。
带跳的随机泛函人口模型动力学,谭利,侯振挺,文中利用一类带跳的随机泛函Kolmogorov模型来描述人口模型动力学。通过构造特殊的Lyapunov函数,证明了模型存在唯一的全局正解。同时还�
Instead of starting at "Hello World," Wicked Cool PHP assumes that you're familiar with the language and jumps right into the good stuff. After you learn the FAQs of life-the most commonly wished for ...
You are visitor as of October 17, 1996. The Art of Assembly Language Programming <br>Forward Why Would Anyone Learn This Stuff? 1 What's Wrong With Assembly Language 2 What's Right With ...
But the audiences will not leave until the ticket price jumps up a complete step of p yuans. For example, if given p=1.00 and m=10, no audience will be lost if the price is set to be 0.99 yuans, and ...
带跳扩散过程的随机序及其应用,张新生,,本文讨论了带跳扩散过程之间的随机序,得到了它们之间的一个比较定理,并利用此定理研究了带跳扩散过程的不变概率测度的存在于唯
reader may feel that the material quickly jumps from a simple overview of Mobile IP or IPsec to sophisticated topics such as bootstrapping for IP mobility or key exchange for IP security. Our ...
Instead of starting at “Hello World,” Wicked Cool PHP assumes that you’re familiar with the language and jumps right into the good stuff. After you learn the FAQs of life – the most commonly ...
This procedure covers the activities from … DEFINITION Terminology 1 The quick brown fox jumps over the lazy dog. The quick brown fox jumps over the lazy dog. Terminology 2 The quick brown fox jumps...
带跳的正向-倒向重随机微分方程的极大值原理,徐树立,蒋君,正倒向随机微分方程在多个领域都有广泛的研究,特别是在经济领域内。由正倒向随机微分方程驱动的最优控制问题的极大值原理已被多
This book skips the beginning level material and jumps right in to Visual C++. By the end of the book, you will be able to master the 32-bit power of Windows using Visual C++ as your programming ...
This book jumps into the world of Hadoop ecosystem components and its tools in a simplified manner, and provides you with the skills to utilize them effectively for faster and effective development of...