c++题目描述 河面上有 N N个木桩排成一排，且每个木桩上都有一个数字，木桩上的数字表示青蛙从当前木桩一次最多可跳跃的木桩个数（例如木桩上的数字为2，青蛙可以跳跃一个木桩也可以跳跃两个木桩）。青蛙只能从第一个木桩向最后一个木桩的方向跳跃。请你帮助青蛙计算出从第一个木桩跳跃到最后一个木桩最少需要跳跃几次，以及有多少跳跃路线可以用最少跳跃次数跳到最后最后一个木桩。 例如： N = 5 N=5，5个木桩上的数字分别为2，1，5，1，3。 第一次跳跃，青蛙从第一个木桩跳跃到第三个木桩，共跳了2个木桩； 第二次跳跃，青蛙从第三个木桩跳跃到最后一个木桩，共跳了2个木桩； 故最少需要跳跃2次可到达最后一个木桩。跳跃2次到最后一个木桩的跳跃路线只有这1种。 输入描述 第1行，1个正整数 N N 第2行， N N个正整数 a 1 , a 2 , ⋯   , a N a 1 ​ ,a 2 ​ ,⋯,a N ​ ，表示每个木桩上的数 输出描述 第1行输出最少跳跃次数。 第2行输出最短跳跃路线数除以 1 0 9 + 7 10 9 +7 的余数。

### C++ 动态规划实现青蛙跳跃问题 #### 问题背景 在动态规划领域，青蛙跳跃问题是经典的优化类题目之一。假设一只青蛙位于台阶 `0` 上，它每次可以选择跳上若干级台阶（通常为固定范围内的任意值）。目标是从起点到达终点，并计算达到该位置所需的最少跳跃次数以及可能的路径总数。 以下是基于动态规划的思想设计的一个解决方案： --- #### 完整代码示例 ```cpp #include <iostream> #include <vector> using namespace std; const long long MOD = 1e9 + 7; // 计算最小跳跃次数和路径数量 pair<long long, long long> frogJump(int n, vector<int>& jumps) { // dp[i].first 表示到达第 i 级台阶的最小跳跃次数 // dp[i].second 表示到达第 i 级台阶的不同路径数量 vector<pair<long long, long long>> dp(n + 1, {INT32_MAX, 0}); // 初始化状态：从地面到第 0 级台阶不需要任何跳跃 dp[0] = {0, 1}; for (int i = 1; i <= n; ++i) { for (auto jump : jumps) { if (i - jump >= 0 && dp[i - jump].first != INT32_MAX) { // 更新最小跳跃次数 if (dp[i].first > dp[i - jump].first + 1) { dp[i].first = dp[i - jump].first + 1; dp[i].second = dp[i - jump].second % MOD; } // 如果跳跃次数相同，则累加路径数量 else if (dp[i].first == dp[i - jump].first + 1) { dp[i].second = (dp[i].second + dp[i - jump].second) % MOD; } } } } return dp[n]; } int main() { int n; cout << "请输入台阶总数: "; cin >> n; vector<int> jumps; cout << "请输入允许的跳跃步数列表（以-1结束输入）：" << endl; int step; while (cin >> step && step != -1) { jumps.push_back(step); } pair<long long, long long> result = frogJump(n, jumps); cout << "最少跳跃次数: " << result.first << endl; cout << "不同路径数量: " << result.second << endl; return 0; } ``` --- #### 关键点解析 1. **动态规划数组定义** 使用二维数组 `dp[i][j]` 来记录状态： - `dp[i].first`: 到达第 `i` 级台阶所需要的最少跳跃次数。 - `dp[i].second`: 到达第 `i` 级台阶的不同路径数量[^6]。 2. **初始化条件** 设定初始状态为 `dp[0] = {0, 1}`，即从地面到第 `0` 级台阶无需跳跃，且只有一种方式完成此过程。 3. **转移方程** 对于每一个台阶 `i` 和每一种可能的跳跃距离 `jump`，如果可以从之前的某一步跃至当前台阶，则更新其跳跃次数与路径数量： - 若发现更优解（较少的跳跃次数），则替换原有数据并重置路径计数； - 若存在多条最优路径，则累计这些路径的数量[^7]。 4. **模运算处理大数溢出** 因为路径数目可能会非常庞大，在实际应用中采用取余操作 `%MOD` 防止超出整型范围[^8]。 --- #### 性能评估 时间复杂度主要由外层遍历台阶数 `O(N)` 及内嵌循环尝试各种跳跃长度决定，总体为 \( O(N \times M) \)，其中 \( N \) 是总台阶数，\( M \) 是可用跳跃种类数。空间消耗同样依赖于存储整个 DP 数组的空间需求，即 \( O(N) \)[^9]。 ---