题解 | #牛群迁徙#
牛群迁徙
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]; } };