描述一个nxm的网格中,起点在(1,1),终点在(n,m),网格中有一块不能走的矩形区域,左下坐标为(x0,y0),右上坐标为(x1,y1),求从起点到终点的路径条数。   示例1 输入:4,4,2,2,3,3返回值:2说明:只有两条可达路径思路 这道题是求从起点到一个格子的所有路径。大家看上面的红点所在的格子,想要到红点所在的格子有两条路:一是:从红点左侧的格子过来;二是:从红点下侧的格子过来;然后我想要知道 红点 左侧格子有几条路径,也是用同样的方法。这样看来,我想求某个格子的路径数量应该是如下公式:       dp[m][n] = dp[m - 1][n] + dp[m][n - 1];    dp[m][n]: 某个格子的坐标;    dp[m - 1][n]:是格子左侧的格子路径数量;    dp[m][n - 1]:是格子下侧的格子路径数量;  这么就是动态规划的 状态转移方程。动态规划除了状态转移方程还有一个重要的元素,那就是 初始值。这道题的初始值很好确定,dp[1][1] = 1。就是起点位置默认是一条路径。   AC代码 public int GetNumberOfPath (int n, int m, int x0, int y0, int x1, int y1) {        // write code hereå        if (m < 1 || n < 1) {            return 0;        }        // 初始化dp数组        int[][] dp = new int[n + 1][m + 1];å        // 设置默认值        dp[1][1] = 1;        // 开始遍历所有格子        for (int i = 1; i <= n; i ++) {            for (int j = 1; j <= m; j ++) {                if (i == 1 && j == 1) {                    continue;                }                // 当遇到不能走的区域 跳过                if (i >= x0 && i <= x1 && j >= y0 && j <= y1) continue;                // 每个格子的路径条数 = 左侧数量 + 下侧数量                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1])%1000000007;            }        }        return dp[n][m];    } 时间复杂度:O(m*n), m 和 n 分别是长宽,因为所有的格子都要遍历到。   空间复杂度:O(m*n),要将这些格子存储到 dp[m][n],二维数组中。  最后  更多的刷题已经知识,大家可以来我的博客看一看
点赞 0
评论 0
全部评论

相关推荐

点赞 评论 收藏
分享
07-03 16:13
嘉应学院 Python
xiaolihuam...:很明显骗子,如果是hr直接约你面试了,哪用得着内推,如果是员工的话,你得多优秀,一线员工直接加你微信,
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务