Untitled

 avatar
unknown
plain_text
a year ago
1.2 kB
5
Indexable
class Solution {
    public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
        long[][] dp = new long[m][n];

        long sumHorizontal = 0;
        for (int i = 0; i <= m-1; i++) {
            if (i >= 1) {
                sumHorizontal += horizontalCut[i - 1];
            }
            long sumVertical = 0;
            for (int j = 0; j <= n-1; j++) {
                if (j >= 1) {
                    sumVertical += verticalCut[j - 1];
                }

                    if (i == 0) {
                        dp[i][j] = sumVertical;
                    } else if (j == 0) {
                        dp[i][j] = sumHorizontal;
                    } else {
                        dp[i][j] = Math.min(
                                dp[i - 1][j] + horizontalCut[i-1] * (j+1),
                                dp[i][j - 1] + verticalCut[j-1] * (i+1)
                        );
                    }    

            }
        }

        return dp[m - 1][n - 1];
    }

    public static void main(String[] args) {
        var x = new Solution();
        System.out.println(x.minimumCost(3, 2, new int[]{1, 3}, new int[]{5}));
        ;
    }
}
Editor is loading...
Leave a Comment