狗家电话面试

wythhh 发表于 2018-8-26 02:05
楼主你咋优化的呢？我感觉这题无论是二维dp还是暴力解法(遍历string，然后对于每个char向左右方向继续找)的 ...

可简化成一维dp

uncle Max 发表于 2018-8-11 23:16
请问楼主 oa 考的什么 正在准备他家的oa

没有oa ........

b989011 发表于 2018-9-1 05:12
可简化成一维dp

变成一维DP是指dp[m][n]变成dp[m*n]吗？如果是的话 好处是啥？

sweetwater 发表于 2018-9-25 04:25
变成一维DP是指dp[m][n]变成dp[m*n]吗？如果是的话 好处是啥？

不是的，是变成dp[n]
原本用dp[m][n]做到后面可以发现，当在row m时，前面row 0 ~ m-2的讯息不需要了，因此可以重複利用这个dp[n]来储存讯息。

b989011 发表于 2018-10-13 05:14
不是的，是变成dp[n]
原本用dp[m][n]做到后面可以发现，当在row m时，前面row 0 ~ m-2的讯息不需要了， ...

是用滚动数组把dp[n][n]变成dp[2][n]吗？