leetcode 耗时100 1824. Minimum Sideway Jumps-北京尧图网络

Problem: 1824. 最少侧跳次数三种方案的1、动态规划的就三种情况先拿到前一列到当前列的最小跳跃次数也就是copy然后计算同一列之间跳跃的最小值2、动态规划的空间优化版本只需要保存前一列的值3、回溯记忆化搜索可以做耗时100方案1Codeclass Solution { public: int n; int minSideJumps(vectorint obstacles) { n obstacles.size(); vectorvectorint dp(4, vectorint(n 1, INT_MAX/10)); dp[1][0] 1; dp[2][0] 0; dp[3][0] 1; for(int i 1; i n; i) { for(int j 1; j 4; j) { if(j ! obstacles[i-1]) { dp[j][i] min(dp[j][i-1], dp[j][i]); } } if(obstacles[i] 0) { dp[1][i] min(dp[1][i], dp[2][i] 1); dp[1][i] min(dp[1][i], dp[3][i] 1); dp[2][i] min(dp[2][i], dp[1][i] 1); dp[2][i] min(dp[2][i], dp[3][i] 1); dp[3][i] min(dp[3][i], dp[1][i] 1); dp[3][i] min(dp[3][i], dp[2][i] 1); } else if(obstacles[i] 1) { dp[2][i] min(dp[2][i], dp[3][i] 1); dp[3][i] min(dp[3][i], dp[2][i] 1); } else if(obstacles[i] 2) { dp[1][i] min(dp[1][i], dp[3][i] 1); dp[3][i] min(dp[3][i], dp[1][i] 1); } else if(obstacles[i] 3) { dp[1][i] min(dp[1][i], dp[2][i] 1); dp[2][i] min(dp[2][i], dp[1][i] 1); } } return min({dp[1][n-1], dp[2][n-1], dp[3][n-1]}); } };方案2Codeclass Solution { public: int minSideJumps(vectorint obstacles) { int n obstacles.size(); int mxmx INT_MAX/10; int a1 mxmx, a2 mxmx, a3 mxmx; int pa1, pa2, pa3, t1, t2, t3; pa1 1; pa2 0; pa3 1; for(int i 1; i n; i) { if(obstacles[i-1]!1) t1 pa1; else t1 mxmx; if(obstacles[i-1]!2) t2 pa2; else t2 mxmx; if(obstacles[i-1]!3) t3 pa3; else t3 mxmx; a1 t1; a2 t2; a3 t3; if(obstacles[i] 0) { a1 min(a1, t2 1); a1 min(a1, t3 1); a2 min(a2, t1 1); a2 min(a2, t3 1); a3 min(a3, t1 1); a3 min(a3, t2 1); } else if(obstacles[i] 1) { a2 min(a2, t3 1); a3 min(a3, t2 1); a1 mxmx; } else if(obstacles[i] 2) { a1 min(a1, t3 1); a3 min(a3, t1 1); a2 mxmx; } else if(obstacles[i] 3) { a1 min(a1, t2 1); a2 min(a2, t1 1); a3 mxmx; } pa1 a1; pa2 a2; pa3 a3; } return min({pa1, pa2, pa3}); } };

leetcode 耗时100 1824. Minimum Sideway Jumps

相关推荐

Ubuntu下IGH与TwinCAT3双主站调试零差云控EtherCAT电机实战

ARM7 VIC伪中断实战解析：从示波器波形到三读取加固

AI Agent工具开发实战：层层护栏防止删库跑路

更多资讯

迪文DMG80480C070工业串口屏调试全指南：变量驱动、字库分离与RS485抗干扰

ROS2 Jazzy 包管理极简实战：创建、编译、运行一条龙

电商平台软件架构设计：从业务边界到微服务落地实践

AI 创新合伙人公会：用体系化机制破解 AI 创业的六大落地难题

华硕X99上Tesla M40无法点亮？一文搞懂Above 4G Decoding设置

Allegro SPB17.4铺铜后Solder Mask DRC报错排查与规则设置指南

今日更新

Play Framework 迁移指南：移除 GlobalSettings，全面转向依赖注入（Scala 与 Java）

Numba 类型推断机制详解：从 Numba IR 到编译期类型重建的完整原理与实践

企业级项目dragonballz_e159-1的技术架构与实现方案

本周精选

深入解析Transformer多头注意力机制与工程优化

OpenClaw 的 Skills 跑学习任务，模型通道改到 TaoToken 通道行不行？

ChatGPT报错Oops, an error occurred! 全链路排查指南

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？