9.29【A】

2267暴力DFS超时使用DFS记录左括号的数量不断遍历向右与向下当遇到右括号数量大于左括号时就说明非法最后到终点时检测左括号和右括号数量是否一致写地很优雅但是超时了如果使用数组来记忆化不知道能否不超时以及对于m,n均小于100的情况也会超时dfs的复杂度是怎样的记忆化确实加个记忆化就解决问题了此外还有一个关键优化就是对lnum和rnum维度的合并对于路径长度即走过格子数量的计算考虑长宽为m,n那么外围的半边周长就是mn,格子数量减去边角的重叠就是mn-1,然后换算到下标那就是xy1了由此可以把原来四维的状态无损地缩放到三维