福州网站建设多少钱,上海专业网站制作设计公司,网站空间编辑器,wordpress多站点的路径本文已收录于专栏#x1f338;《Java入门一百例》#x1f338;学习指引序、专栏前言一、网格模型二、【例题1】1、题目描述2、解题思路3、模板代码4、代码解析5.原题链接三、【例题2】1、题目描述2、解题思路3、模板代码4、代码解析5.原题链接三、推荐专栏四、课后习题序、专…本文已收录于专栏《Java入门一百例》学习指引序、专栏前言一、网格模型二、【例题1】1、题目描述2、解题思路3、模板代码4、代码解析5.原题链接三、【例题2】1、题目描述2、解题思路3、模板代码4、代码解析5.原题链接三、推荐专栏四、课后习题序、专栏前言 本专栏开启目的在于帮助大家更好的掌握学习Java特别是一些Java学习者难以在网上找到系统地算法学习资料帮助自身入门算法同时对于专栏内的内容有任何疑问都可在文章末尾添加我的微信给你进行一对一的讲解。 但最最主要的还是需要独立思考对于本专栏的所有内容能够进行完全掌握自己完完全全将代码写过一遍对于算法入门肯定是没有问题的。 算法的学习肯定不能缺少总结这里我推荐大家可以到高校算法社区将学过的知识进行打卡以此来进行巩固以及复习。 学好算法的唯一途径那一定是题海战略大量练习的堆积才能练就一身本领。专栏的任何题目我将会从【题目描述】【解题思路】【模板代码】【代码解析】等四板块进行讲解。
一、网格模型 网格模型是一个很经典的模型也可以称之为数字三角形模型。其一般形态就是在一个二维的网格中以左上角为起点到右下角为终点只能往下走或者往右走。求得这个过程中可以获取的不同路径数或者权值最大最小问题当然如何移动也要根据题意来分析在转移时亦是如此。今天将带来两道最入门的网格dp入门题。
二、【例题1】
1、题目描述
一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。
问总共有多少条不同的路径
2、解题思路 定义 f[i][j]f[i][j]f[i][j] 为走到 iii 行 jjj 列的不同路径数显然 iii 行 jjj 列只能从i−1i-1i−1 行 jjj 列和iii 行 j−1j-1j−1 列走过来那么具有转移方程 f[i][j]f[i−1][j]f[i][j−1]f[i][j]f[i-1][j]f[i][j-1]f[i][j]f[i−1][j]f[i][j−1] 初始化时f[1][1]f[1][1]f[1][1]应该等于1答案即是f[m][n]f[m][n]f[m][n]
3、模板代码
class Solution {public int uniquePaths(int m, int n) {int[][] fnew int[m1][n1];f[1][1]1;for(int i1;im;i){for(int j1;jn;j){if(i1j1) continue;f[i][j]f[i-1][j]f[i][j-1];}}return f[m][n];}
}使用滚动数组优化:
class Solution {public int uniquePaths(int m, int n) {int[] fnew int[n1];f[1]1;for(int i1;im;i){for(int j1;jn;j){if(i1j1) continue;f[j]f[j-1];}}return f[n];}
}4、代码解析
滚动数组优化也是二维dp里常用的优化方式可以帮忙我们压缩一维空间不太理解暂时不建议深究。 为了防止边界越界问题这里大家 iii jjj 都从1开始如果从0的话在转移时会出现越界。
5.原题链接
不同路径
三、【例题2】
1、题目描述
一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish”。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径
网格中的障碍物和空位置分别用 1 和 0 来表示。
2、解题思路
转移方程和上面是相同的不同由于存在障碍物只有在 i,ji,ji,j 不是障碍物时我们才进去转移才行同样为了防止边界越界我们 dp 时下标同样从1开始。
3、模板代码
class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int mobstacleGrid.length;int nobstacleGrid[0].length;int[][] fnew int[m1][n1];if(obstacleGrid[0][0]0)f[1][1]1;for(int i1;im;i){for(int j1;jn;j){if(i1j1) continue;if(obstacleGrid[i-1][j-1]0)f[i][j]f[i-1][j]f[i][j-1];}}return f[m][n];}
}4、代码解析
注意起点有可能有石头初始化时需要进行判断。
5.原题链接
不同路径||
三、推荐专栏
《零基础学算法100天》四、课后习题
序号题目链接难度评级1 最小路径和3学习有疑问
