1.网抑云题 一个是进行字符串补全使之成为回文串 AC70% 另一个是一堆物品平均分给两个人 (允许丢弃) 求最少丢弃
字符串补全为回文串的
我的做法是 动态规划 判断if(s[i]==s[j])
是的话就
dp[i][j]=dp[i+1][j-1]
否则 的话就是我们的
dp[i][j]=dp[i+1][j]
要注意的是对于动态规划 状态转移来计算dp[i][j]的时候要从小到大 否则前面计算好的可能被后面的计算覆盖掉
先计算边缘 dp[i][i] 然后增大 如果你直接去计算大的可能结果就是说 每个晓得都是0 计算的大的也一样 动态规划是从小往上积累的
#include<iostream>
#include<vector>
using namespace std;
int main() {
int dp[1005][1005];
int n;
for (int i = 0;i < n;i++) {
dp[i][i] = 0;
}
for (int j = 1;j< n ;j++) {
for (int i = j-1;i >-1;i--) {
if (s[i]