题解 | #牛群迁徙#
牛群迁徙
https://www.nowcoder.com/practice/686d79ac54874f5f8abbb83184102873
考察的知识点：动态规划；
解答方法分析：
- 定义一个数组dp，dp[i]表示到达第i个河流所需要的最小跳跃次数。
- 初始状态下，dp[0]为0，因为初始位置已经在第一个河流处。
- 从第一个河流开始，遍历rivers数组。对于第i个河流，需要找到前面的所有河流中能够跳跃到当前河流的最小跳跃次数。因此，遍历从0到i-1的所有河流，找到能够跳跃到当前河流的索引j，并更新dp[i]为dp[j]+1。
所用编程语言：C++；
完整编程代码：↓
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param rivers int整型vector
* @return int整型
*/
int min_jumps(vector<int>& rivers) {
int n = rivers.size();
vector<int> dp(n, INT_MAX);
dp[0] = 0;
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (j + rivers[j] >= i) {
dp[i] = min(dp[i], dp[j] + 1);
}
}
}
return dp[n - 1];
}
};
海康威视公司福利 1382人发布
