11/23 狗家 onsite

catinclay 发表于 2016-11-26 09:23
哈哈 我說的二維dp是palindrome那題
另一題確實是要三維dp

请问怎么二维啊。没啥思路，只想到一个N^3的解答

waikai 发表于 2016-11-26 10:32
请问怎么二维啊。没啥思路，只想到一个N^3的解答

```
dp[l][r] 代表 substring(l,r)所需要的最少插入
if(char[l] == char[r]), dp[l][r] = dp[l+1][r-1]  // 把char[l]跟char[r]都去掉
if(char[l] != char[r]), dp[l][r] = min(dp[l][r-1], dp[l+1][r])+1 //把char[l]或char[r]插入到另一邊, 取比較小的
```

moonstone 发表于 2016-11-26 06:19
第三题
skip is the min distance end at i(i is skipped) with j skips
noSkip is the min distance end ...

wow, 這樣好像可以二維dp解.... awesome

补充内容 (2016-11-26 13:13):
不對...看了一下 好像會有問題..

补充内容 (2016-11-26 13:19):
關鍵在noSkip[i,j]不一定會由 skip[i - 1, j - 1] + dst[sLast[i - 1, j - 1], i] 組成

catinclay 发表于 2016-11-26 13:03
```
dp[l][r] 代表 substring(l,r)所需要的最少插入
if(char[l] == char[r]), dp[l][r] = dp[l+1][r-1] ...

明白了。谢谢。就是第二个if好像不应该用，对于char[l] == char[r]的时候也需要检查 dp[l][r-1], dp[l+1][r]

catinclay 发表于 2016-11-26 13:11
wow, 這樣好像可以二維dp解.... awesome

补充内容 (2016-11-26 13:13):

为什么呀 能举个反例么

waikai 发表于 2016-11-26 13:30
明白了。谢谢。就是第二个if好像不应该用，对于char[l] == char[r]的时候也需要检查 dp[l][r-1], dp[l+1] ...

額...為什麼？字數字數

moonstone 发表于 2016-11-26 14:08
为什么呀 能举个反例么

假設四個點 1, 2, 3, 4, 跳過兩個點的情況可能是跳過1, 4 最好 但第五個點加進來的時候 有可能是跳過3 4 5更好

补充内容 (2016-11-26 15:16):
說錯了 是可能跳過 2 3 4 更好 因為可能 2 5的distance特大

不知道是不是我理解错了，第四题的话插入的最小个数不就是原字符串里奇数个字符数量减一

补充内容 (2016-11-27 09:23):
无视我，我想到反例了

catinclay 发表于 2016-11-26 15:14
假設四個點 1, 2, 3, 4, 跳過兩個點的情況可能是跳過1, 4 最好 但第五個點加進來的時候 有可能是跳過3 4  ...

但是你跳过2，3，4不是跳过三个点了吗，sLast和跳两个点的情况是不一样的吧？
对于1，2，3，4没有办法跳过三个点，所以三个点对于1，2，3，4，5是新的情况，再加一个判断应该可以吧。我感觉二维dp应该是够的

补充内容 (2016-11-27 10:00):
就是noSkip(i, j) 增加一个 dst(i-j-1, i) 的最小值candidate

把第三面的題目試了寫了, 用的是二維dp但複雜度是n^3
試著加了comment, 但感覺解釋的不太好..要是有人看懂了覺得可以解釋得更好的可以給我些comment意見
要是看不懂的可以一起討論下

1.         // getShortestDistance(點的數量, 可跳過的點的數量, 距離矩陣)
   
2.         // dis[i][j] 代表node i 與 node j的距離
   
3.         // 點的數量n 代表點的編號為 1, 2, 3, 4...n
   
4.         public static int getShortestDistance(int n, int skipNum, int[][] dis){
   
5. 
   
6.                 // dp[當前path的最後一個點][跳過點的數量]
   
7.                 int[][] dp = new int[n+1][skipNum+1];
   
8. 
   
9.                 // 初始化所有“不跳過任何點”的距離
   
10.                 for(int i = 1; i <= n;++i){
    
11.                         dp[i][0] = dp[i-1][0] + dis[i-1][i];
    
12.                 }
    
13. 
    
14.                 // 處理node(i), 也就是以node(i) 為path最後一個點的情況
    
15.                 // 從node(1) 開始處理到node(n)
    
16.                 for(int i = 1; i <= n; ++i){
    
17. 
    
18.                         // 跳過了j個點
    
19.                         // 從跳過1個node開始到處理跳過skipNum個node
    
20.                         for(int j = 1; j <= skipNum && j < i;++j){
    
21. 
    
22.                                 // 不跳過第node(n-1) 的情況, 距離為dp[i-1][j] + dis[i-1][i]
    
23.                                 dp[i][j] = dp[i-1][j]+dis[i-1][i];
    
24. 
    
25.                                 // 最後一個點之前, 連續跳過了k個點的情況
    
26.                                 // eg: k = 2, i = 10的情況, 代表跳過了node (8) 跟node (9)
    
27.                                 // 此時距離會是:
    
28.                                 // 處理到node(7), 跳過j-2個點 + node(7)到node(10)的距離 (跳過兩個點, 8與9)
    
29.                                 //       dp[7][j-2]         +        dis[7][10]
    
30.                                 for(int k = 1; k <= j; ++k){
    
31.                                         // 把k=1~j的所有情況取最小值
    
32.                                         // dp[i-k-1][j-k]
    
33.                                         dp[i][j] = Math.min(dp[i][j], dp[i-k-1][j-k] + dis[i-k-1][i]);
    
34.                                 }
    
35.                         }
    
36.                 }
    
37. 
    
38.                 // 把所有處理到node(n)的情況取最小值
    
39.                 // path的最後一個點從node(n - skipNum) ~ node(n) 都有可能, 這裏用k當作變數
    
40.                 int ans = Integer.MAX_VALUE;
    
41.                 for(int k = n-skipNum; k <= n; ++k){
    
42.                         // 跳過的node數則會是skipNum-(n-k)
    
43.                         // eg: 假如最後一個node是 node(n-2), 及代表node(n-1)跟node(n)被跳過
    
44.                         // 此時要看的就是dp[n-2][skipNum-2]
    
45.                         ans = Math.min(ans, dp[k][skipNum-(n-k)]);
    
46.                 }
    
47.                 return ans;
    
48.         }
    
49. 
    
50. }

复制代码