讨论/题目交流/🏆 第 153 场力扣周赛/
🏆 第 153 场力扣周赛

这是 9 月的第二场周赛,欢迎小伙伴们在这里交流分享你的参赛心得以及体验。

image.png

展开讨论
力扣 (LeetCode)发起于 2019-09-08

分享一下第四题的做法~

题意:给定一个数组 arr1arr1,操作可以将 arr1arr1 中数字变换为 arr2arr2 中数字,问将 arr1arr1 变为一个严格升序的数组的最小操作次数。

首先,一个很明显的贪心是,如果我们要确定对 arr1[i],i>1arr1[i], i>1 进行操作,那么我们一定选择一个最小的 karr2k \in arr2 且满足 k>arr1[i1]k > arr1[i-1]。因为,我们将 arr1[i]arr1[i] 变得越小,之后留给后面的数字的余地就越多。
所以,对于 arr1arr1 中的一个数字,只有两个选择:不变 / 变成 arr2arr2 中最小的大于它的数字。

这样,就可以动态规划了,定义 DP[i][j]DP[i][j] 表示将 arr1arr1 中的第 ii 个数字变为 arr2arr2 中的第 jj 个数字后(可以设定一个特殊的 jj 表示 arr1[i]arr1[i] 不变),满足 arr1[1i]arr1[1\cdots i] 严格升序递增的最小操作次数。
转移方程就是对于所有的 dp[i][j]dp[i][j],枚举第 arr1[i+1]arr1[i+1] 是否变化,然后进行转移就可以了。(转移详情见代码)

int pool[2050];
int dp[2050][2050];
class Solution {
public:
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        int n=arr1.size(), m=arr2.size();
        
        for (int i=0; i<m; i++) pool[i]=arr2[i];
        sort(pool, pool+m);
        m=unique(pool, pool+m)-pool;
        
        memset(dp, -1, sizeof(dp));
        dp[0][m]=0; for (int i=0; i<m; i++) dp[0][i]=1;
        for (int i=0; i<n-1; i++){
            for (int j=0; j<=m; j++){
                if (dp[i][j]==-1) continue;
                int now_v=(j==m?arr1[i]:pool[j]);
                // Don't
                if (arr1[i+1]>now_v){
                    if (dp[i+1][m]==-1 || dp[i+1][m]>dp[i][j]) dp[i+1][m]=dp[i][j];
                }
                // Modify
                int nxt_p=upper_bound(pool, pool+m, now_v)-pool;
                if (nxt_p<m){
                    // printf("Change(%d) %d->%d\n", i, arr1[i], pool[nxt_p]);
                    if (dp[i+1][nxt_p]==-1 || dp[i+1][nxt_p]>dp[i][j]+1) dp[i+1][nxt_p]=dp[i][j]+1;
                }
            }
        }
        
        int ans=-1;
        for (int i=0; i<=m; i++){
            if (dp[n-1][i]==-1) continue;
            if (ans==-1 || ans>dp[n-1][i]) ans=dp[n-1][i];
        }
        
        return ans;
    }
};
15
展开全部 17 讨论