电子商务网站建设实训实践总结推荐定制型网站建设

电子商务网站建设实训实践总结,推荐定制型网站建设,网络服务广告,宝安做网站的一、 问题描述一只青蛙想要过河#xff0c;河流被等分为若干个单元格#xff0c;每个单元格内可能放有一块石子#xff08;也可能没有#xff09;。青蛙只能跳上石子#xff0c;不能跳入水中。给定石子的位置列表 stones#xff08;用单元格序号升序表示#xff09;河流被等分为若干个单元格每个单元格内可能放有一块石子也可能没有。青蛙只能跳上石子不能跳入水中。给定石子的位置列表 stones用单元格序号升序表示需要判断青蛙能否成功过河即能否在最后一步跳至最后一块石子上。约束条件1. 开始时青蛙默认已站在第一块石子上2. 第一步只能跳跃 1 个单位从单元格 1 跳至单元格 23. 如果青蛙上一步跳跃了 k 个单位那么接下来的跳跃距离只能选择为 k-1、k 或 k1 个单位4. 青蛙只能向前方终点方向跳跃二、解法思路1. 状态定义定义二维动态规划数组 dp[i][speed]表示能否以 speed 的速度到达第 i 个石子。i石子的索引0-basedspeed到达第 i 个石子时的跳跃速度即从上一次跳跃的距离2. 初始化开始时青蛙静止地站在 0 号石头上因此 dp[0][0] 1表示可以以速度 0 到达起始位置3. 状态转移方程对于每个石子 i我们检查所有之前的石子 jj i计算从 j 跳到 i 的速度speed stones[i] - stones[j]如果能够从石子 j 以某种速度跳到石子 i那么需要满足以下条件1. speed 0只能向前跳2. speed ≤ j 1速度不能超过 j1证明见后状态转移方程如下dp[i][speed] dp[j][speed-1] || dp[j][speed] || dp[j][speed1]这意味着如果从石子 j 出发以 speed-1、speed 或 speed1 的速度跳跃可以到达石子 j那么就可以以 speed 的速度到达石子 i。4. 速度范围证明为什么 speed ≤ j 1假设青蛙从 0 号石子开始每次跳跃速度最多增加 1。到达第 j 个石子时最多进行了 j 次加速从第一次跳跃开始计算因此最大速度不会超过 j。那么从第 j 个石子起跳最大速度不会超过 j1。所以从石子 j 跳到石子 i 的速度 speed 必须满足 speed ≤ j1。代码实现cppclass Solution {public:bool canCross(vectorint stones) {int n stones.size();// dp[i][speed]: 表示能否以speed的速度到达第i个石头vectorvectorint dp(n, vectorint(n1, 0));dp[0][0] 1;for(int i 1; i n; i) {for(int j 0; j i; j) {int speed stones[i] - stones[j];// 速度必须为正且不能超过j1if(speed 0 || speed j1)continue;// 状态转移dp[i][speed] dp[j][speed-1] || dp[j][speed] || dp[j][speed1];// 如果已经到达最后一个石子直接返回trueif(i n-1 dp[i][speed] 1)return true;}}return false;}};算法分析时间复杂度1.外层循环遍历所有石子O(n)2. 内层循环对于每个石子 i遍历所有 j iO(n)3. 总时间复杂度O(n²)空间复杂度-dp数组大小为 n × (n1)O(n²)性能表现根据测试结果执行用时320 ms击败 23.86% 的 C 用户内存消耗226.5 MB击败 5.04% 的 C 用户总结青蛙过河问题是一个典型的动态规划问题通过定义合适的状态和状态转移方程可以有效地解决。虽然基本的动态规划解法在时间复杂度和空间复杂度上都有优化空间但它清晰地展示了问题的解决思路。对于这类问题关键点在于1. 正确理解问题约束条件2. 设计合适的状态表示3. 找到正确的状态转移关系4. 注意边界条件的处理