facebook 电话＋onsite

zhonghuazai 发表于 2017-11-9 05:16
不知道是不是我题意理解错了，初始位置在0，假如只能走一步的话，只能到5或者7，那就是只有两种走法。按 ...

同感！除非题目是从任意点开始走

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

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

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

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

chengshuangdao 发表于 2017-11-9 10:41
如果起始是0的话，最好用那种top-down的dp，用递归写dfs，但是用一个dp数组储存子路径的结果，应该比我这 ...

其实我觉得完全不用dp， 直接dfs就可以了。

zhonghuazai 发表于 2017-11-15 12:03
其实我觉得完全不用dp， 直接dfs就可以了。

可以用dp数组储存重复运算的结果，可以修剪dfs搜索树的大小

还是写了一下，类似于这样

1. public int numOfPaths(int n) {
   
2.     int[][] dp = new int[n][10];
   
3.     return dfs(n, 0, dp);
   
4.   }
   
5.   
   
6.   private int dfs(int n, int curr, int[][] dp) {
   
7.     if(n == 0) return 1;
   
8.     if(dp[n-1][curr] > 0) return dp[n-1][curr];
   
9.    
   
10.     if(curr == 0) {
    
11.       dp[n-1][curr] = dfs(n-1, 5, dp) + dfs(n-1, 7, dp);
    
12.     }else if(curr == 1) {
    
13.       dp[n-1][curr] = dfs(n-1, 6, dp) + dfs(n-1, 8, dp);
    
14.     }else if(curr == 2) {
    
15.       dp[n-1][curr] = dfs(n-1, 3, dp) + dfs(n-1, 7, dp);
    
16.     }else if(curr == 3) {
    
17.       dp[n-1][curr] = dfs(n-1, 2, dp) + dfs(n-1, 8, dp) + dfs(n-1, 9, dp);
    
18.     }else if(curr == 4) {
    
19.       dp[n-1][curr] = 0;
    
20.     }else if(curr == 5) {
    
21.       dp[n-1][curr] = dfs(n-1, 0, dp) + dfs(n-1, 6, dp) + dfs(n-1, 9, dp);
    
22.     }else if(curr == 6) {
    
23.       dp[n-1][curr] = dfs(n-1, 1, dp) + dfs(n-1, 5, dp);
    
24.     }else if(curr == 7) {
    
25.       dp[n-1][curr] = dfs(n-1, 0, dp) + dfs(n-1, 2, dp);
    
26.     }else if(curr == 8) {
    
27.       dp[n-1][curr] = dfs(n-1, 1, dp) + dfs(n-1, 3, dp);
    
28.     }else{
    
29.       dp[n-1][curr] = dfs(n-1, 3, dp) + dfs(n-1, 5, dp);
    
30.     }
    
31.    
    
32.     return dp[n-1][curr];
    
33. 
    
34.   }

复制代码