11/23 狗家 onsite

1.         public int minDistance(int[][] dist, int k) {
   
2.                 int n = dist.length;
   
3.                 int[][] skip = new int[n][n];
   
4.                 int[][] noSkip = new int[n][n];
   
5.                 int[][] last = new int[n][n];
   
6.                 for (int i = 1; i < n; i ++) {
   
7.                         skip[i][0] = skip[i - 1][0] + dist[i - 1][i];
   
8.                         noSkip[i][0] = noSkip[i - 1][0] + dist[i - 1][i];
   
9.                         last[i][0] = i - 1;
   
10.                 }
    
11.                 for (int i = 1; i < n; i ++) {
    
12.                         for (int j = 1; j <= Math.min(i, k); j ++) {
    
13.                                 skip[i][j] = Math.min(noSkip[i - 1][j - 1], skip[i - 1][j - 1]);
    
14.                                 noSkip[i][j] = Math.min(skip[i - 1][j] + dist[last[i - 1][j]][i], noSkip[i - 1][j] + dist[i - 1][i]);
    
15.                                 last[i][j] = skip[i - 1][j - 1] < noSkip[i - 1][j - 1] ? last[i - 1][j - 1] : i - 1;
    
16.                         }
    
17.                 }
    
18.                 int result = Integer.MAX_VALUE;
    
19.                 for (int j = 0; j <= k; j ++) {
    
20.                         result = Math.min(result, Math.min(skip[n - 1][j]), noSkip[n - 1][j]);
    
21.                 }
    
22.                 return result;
    
23.         }

复制代码

LZ, 第一题“"a234"为啥不能decode成234个a? 请问encode的具体规则？

您好！
本帖隐藏的内容需要积分高于 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