百度后端笔试

第三题服了

随机数整了38

b卷第三题数对象真是大开眼界

卧槽 昨天刚笔试，今天就约面了 百度效率杠杠的

所以第三题dp为啥只有20

百度b卷第三题找对象什么鬼？直接输出一个5，7.69%到手，拜拜👋

第二题对称数组怎么做呢，贪心只过了30

好难啊 第二题只有38 第三题打得累死就50

唉 第三题直接dp20%会超时，可改进，刚刚列出公式应该可行，但是笔试的时候没时间写完了，笔试完试了下测试用例没问题。 dp[i][j][0]表示从左侧到达当前位置的方案数，dp[i][j][1]表示从上侧到达当前位置的方案数。 以dp[3][5]为例（这里的dp指的方案数和，即dp[i][j]=dp[i][j][0]+dp[i][j][1]）， 它等于( dp[2][5]+dp[0][5] )         +   ( dp[3][4]+dp[3][2]+dp[3][0] ),   又有 dp[1][5] = ( dp[0][5] ) + ( dp[1][4] + dp[1][2] ),  dp[3][3] = ( dp[3][2] + dp[3][0] ) + ( dp[2][3] + dp[0][3] )。 发现dp[3][5][0] = dp[3][3][0] + dp[3][4],  dp[3][5][1] = dp[1][5][1] + dp[2][5]。 初始条件：        dp[0][0][0]=0; dp[0][1][0]=1; dp[0][0][1]=0; dp[1][0][1]=1; dp[0][i][0]=dp[0][j-1][0]+dp[0][j-2][0]; dp[i][0][1]=dp[i-1][0][1]+dp[i-2][0][1];   有转移方程： dp[i][j][0]=dp[i][j-2][0] + (dp[i][j-1][0]+dp[i][j-1][1] ); dp[i][j][1]=dp[i-2][j][1] + (dp[i-1][j][0]+dp[i][j][1] ); 这样就少了很多迭代了 return dp[n-1][m-1][0]+dp[n-1][m-1][1];

他真的有offer吗，我都没去做