滴滴笔试

直接sout5也是百分之9，hhh

我的方法：二维dp，dp[i][j]表示从i到j的字符串最大花费，dp[i][j]=max(dp[i][j],dp[i+1][j-1]),然后再用k从i到j遍历，dp[i][j]=max(dp[i][j],dp[i][k-1]+dp[k][j])

我和你情况一样，我贪心但是不懂为什么错也 0.9 😅

DFS过了27，DP好难想

第二题一开始用动规，只过了18，换成递归过了27，不懂

这个思路有问题吗？

我这个哪里有问题呢？#include<bits/stdc++.h>using namespace std;const int N=30;int mp[N][N];char s[600];int n,k;int f[600][600];int main(){ cin>>n>>k; for(int i=0;i<k;i++) { for(int j=0;j<k;j++) { cin>>mp[i][j]; } } cin>>s+1; for(int i=0;i<=n;i++) { for(int j=1;j+i-1<=n;j++){ if(i==2){ f[j][i]=mp[s[j]-'a'][s[j+1]-'a']; } if(i>2){ f[j][i]=max(f[j][i-2]+mp[s[j+i-1]-'a'][s[j+i-2]-'a'],f[j+1][i-2]+mp[s[j]-'a'][s[i+j-1]-'a']); f[j][i]=max(f[j][i],mp[s[j]-'a'][s[j+1]-'a']+f[j+2][i-2]); } } } cout<<f[0][n]<<endl; return 0;}