腾讯五十题 No.20 不同路径
2022/2/7 6:12:41
本文主要是介绍腾讯五十题 No.20 不同路径,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接
递归
class Solution { public int uniquePaths(int m, int n) { return dfs(new HashMap<Pair,Integer>(),0,0,m,n); } private int dfs(Map<Pair,Integer> cache,int i,int j,int m,int n){ Pair p = new Pair(i,j); //如果(i,j)在缓存中就返回这个点 if(cache.containsKey(p)){ return cache.get(p); } //到达边界就返回1 if(i == m-1 || j == n-1){ //成功到达,路径和加一 return 1; } //调用递归,往下i+1,往右j+1 cache.put(p,dfs(cache,i+1,j,m,n)+dfs(cache,i,j+1,m,n)); System.out.println(cache.get(p)); return cache.get(p); } }
动态规划
class Solution { public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; //第一行都赋予 1 for(int i = 0; i < m; ++i) { dp[i][0] = 1; } //第一列都赋予 1 for(int j = 0; j < n; ++j) { dp[0][j] = 1; } //两个for循环推导,对于(i,j)来说,只能由上方或者左方转移过来 for(int i = 1; i < m; ++i) { for(int j = 1; j < n; ++j) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } return dp[m - 1][n - 1]; } }
动归空间优化
class Solution { public int uniquePaths(int m, int n) { //一维空间,其大小为 n int[] dp = new int[n]; Arrays.fill(dp, 1); for(int i = 1; i < m; ++i) { for(int j = 1; j < n; ++j) { //等式右边的 dp[j]是上一次计算后的,加上左边的dp[j-1]即为当前结果 dp[j] = dp[j] + dp[j - 1]; } } return dp[n - 1]; } }
这篇关于腾讯五十题 No.20 不同路径的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?