public class Solution { // C#
    public int MinCost(int n, int[] cuts) {
        int[,] dp = new int[n+1, n+1];
        for (var i = 0; i < n + 1; i++){
            for (var j = 0; j < n + 1; j++){
                dp[i, j] = Int32.MinValue;
            }
        }
        Func<int, int, int> dfs = null;
        dfs = (int lo, int hi) => {
            if (dp[lo, hi] != Int32.MinValue) return dp[lo, hi];
            var filteredCuts = cuts.Where(cut => lo < cut && cut < hi).ToArray();
            if (filteredCuts.Length == 0) return 0;
            int ans = Int32.MaxValue;
            foreach(var mid in filteredCuts){
                ans = Math.Min(ans, dfs(lo, mid) + dfs(mid, hi));
            }
            dp[lo, hi] = ans + hi - lo;
            return dp[lo, hi];
        };
        return dfs(0, n);
    }
}