狗家高频面经求解

看到这题很多次： 从第一行任意一个位置到最后一行

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

讲解dp的思路..

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

1. int n = ch.length;
   
2.             int m = ch[0].length;
   
3.             int[][] dp = new int[n][m];
   
4.             for (int i = 0; i < n; i++) {
   
5.                 for (int j = 0; j < ch[i].length; j++) {
   
6.                     if (ch[i][j] == '.') {
   
7.                         int k = j + 1;
   
8.                         int num = 1;
   
9.                         while (k < m && ch[i][k] == '.') {
   
10.                             k++;
    
11.                             num++;
    
12.                         }
    
13.                         while (j < k) {
    
14.                             dp[i][j] = num;
    
15.                             j++;
    
16.                         }
    
17.                     }
    
18.                 }
    
19.             }
    
20.             for (int i = 1; i < n; i++) {
    
21.                 for (int j = 0; j < m; j++) {
    
22.                     if (ch[i][j] == '.') {
    
23.                         if (ch[i - 1][j] == '.') {
    
24.                             dp[i][j] = dp[i - 1][j] + dp[i][j];
    
25.                         } else {
    
26.                             if (j >= 1)
    
27.                                 dp[i][j] = Math.max(dp[i][j - 1], 0);
    
28.                             else
    
29.                                 dp[i][j] = 0;
    
30.                         }
    
31.                     }
    
32.                 }
    
33.             }

复制代码

[i][i][i][i][i][i][i][i][i]
我这样试了一下，大家看下对吗。
最后在dp最后一行筛选最大返回[/i][/i][/i][/i][/i][/i][/i][/i][/i]

关注一下～

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

感谢！！！！！

狗 电面就是遇到的这道题 相见恨晚

dijkstra可以不可以实现这个算法呢？每个点的长度作为weight？

https://leetcode.com/playground/m6qdqp94

Falldawn 发表于 2021-6-17 06:13
这上面有人说了，感觉就应该是这样做，我改成了Java代码三个数组应该是分别代表从最上面entry行到当前位 ...

按照我的理解可以节省空间而不需要建立一个(m, n)的数组, 因为每次只需要关注连着的两行, 可以节省空间到O(n)