C# dp O(mn^2) still passes OJ


  • 0
    H
    public int SplitArray(int[] nums, int m) {
            int n = nums.Length;
            long[,] dp = new long [m + 1, n];
            
            long s = 0;
            for(int i = 0; i < n; i++) {
                s += (long)nums[i];
                dp[1, i] = s;
            }
            
            for(int i = 2; i <= m; i++) {
                for (int j = i - 1; j < n; j++) {
                    dp[i, j] = dp[1, j];
                    for (int k = i - 2; k < j; k++) {
                        dp[i, j] = Math.Min(dp[i, j], Math.Max(dp[i - 1, k], dp[1, j] - dp[1, k]));
                    }
                }
            }
            
            return (int)dp[m, n - 1];
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.