周赛第三题,知道要用动态规划,但是不知道怎么回到子问题
显然根据题意我们需要让每一列都相同,但是相邻列不能选择同一种数字,观察到数据nums[i]介于0-9,我们就以此为突破口.
首先我们用count[n][10], count[i][j]记录第i+1列值为j的元素个数,转移方程如下:
dfs(i,pre) = max(dfs(i-1,k) + count[i][k]) k=0,1...9 k!=pre;
表示 i 对应的那一列选择k的话, 再去判断i-1对应的那一列的元素
入口是dfs(n-1,10); 使用10是表示没有上一个,取0-9均可
代码如下: 这里写的是 记忆化回溯 ,可以自行改成二维dp
class Solution {
public:
int minimumOperations(vector<vector<int>>& grid) {
int m=grid.size(),n=grid[0].size();
int count[n][10]; //count[i][j] 表示 第i+1列里面值等于j的个数
memset(count,0,sizeof(count));
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
count[j][grid[i][j]]++;
}
}
int memo[n][11];
memset(memo,-1,sizeof(memo));
function<int(int,int)> dfs=[&](int i,int pre){
if(i==-1) return 0;
int &res=memo[i][pre];
if(res!=-1) return res;
int cnt=0;
for(int j=0;j<10;j++){
if(j==pre) continue;
cnt=max(cnt,dfs(i-1,j)+count[i][j]);//[[1,6,7,3,0,4,1,3,7,5]]
}
return res=cnt;
};
return m*n-dfs(n-1,10);
}
};