Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Leetcode 2919. Minimum Increment Operations to Make Array Beautiful #300

Open
Woodyiiiiiii opened this issue Nov 5, 2023 · 0 comments
Open

Comments

@Woodyiiiiiii
Copy link
Owner

Woodyiiiiiii commented Nov 5, 2023

2919. Minimum Increment Operations to Make Array Beautiful

2919. Minimum Increment Operations to Make Array Beautiful

题解:
巧妙设计状态+选或不选(Python/Java/C++/Go)

这道题首先我没想到是DP,其实很容易看得出来的,这是选或不选类型DP。从题目可以看出在3个长度的子数组中一定要保持至少一个数大于等于k。

所以我一开始想着设定dp[i]表示前i个数能完成题目条件的最少操作数。那如何设定状态转移方程呢,从dp[i-1]、dp[i-2]、dp[i-3]可以吗?不行。然后我就没有思路了。

那么其实问题在于设置状态不恰当回想条件,可以利用3,dp[i][j](j <= 2)表示右侧有多少个不满足k的数,这样就可以表示全部状态,同时又容易写出状态转移方程。

这里为了方便改成递推,可以倒着写。

class Solution {
    long[][] dp;
    int n;
    int[] nums;
    int k;

    public long minIncrementOperations(int[] nums, int k) {
        this.n = nums.length;
        dp = new long[n][3];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], -1);
        }
        this.nums = nums;
        this.k = k;
        return dfs(0, 0);
    }

    private long dfs(int i, int j) {
        if (i >= n) {
            return 0;
        }
        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        long ans = dfs(i + 1, 0) + Math.max(0, k - nums[i]);
        if (j < 2) {
            ans = Math.min(ans, dfs(i + 1, j + 1));
        }
        return dp[i][j] = ans;
    }
}

如何改成递推呢?观察状态转移方程,同时注意遍历方向。

class Solution {
    public long minIncrementOperations(int[] nums, int k) {
        long f0 = 0, f1 = 0, f2 = 0;
        for (int x : nums) {
            long inc = f0 + Math.max(k - x, 0);
            f0 = Math.min(inc, f1);
            f1 = Math.min(inc, f2);
            f2 = inc;
        }
        return f0;
    }
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant