C# dp
Intuition\nOne starting from (0, 0) needs to follow main diagonal to reach (n-1, n-1) in n-1 steps.\n\nOther 2 can use different paths, but only up to main diag
# Intuition\nOne starting from (0, 0) needs to follow main diagonal to reach (n-1, n-1) in n-1 steps.\n\nOther 2 can use different paths, but only up to main diagonal, which is covered already. Use dp to find max value.\n\n|||||||\n|-|-|-|-|-|-|\n|1|||||2|\n||1|||2|2|\n|||1|2|2|2|\n|||3|1|2|2|\n||3|3|3|1|2|\n|3|3|3|3|3|1|\n\n\n# Code\n```csharp []\npublic class Solution {   \n    public int MaxCollectedFruits(int[][] fruits) {\n        int total = 0;\n        int n = fruits.Length;\n        int n1 = n - 1;\n\n        for (int i = 0; i < n; i++) {\n            total += fruits[i][i];\n        }\n\n        // Console.WriteLine(total);\n\n        int[] sumsP = new int[0];\n        for (int i = 0; i < n1; i++) {           \n            int[] sums = GetArray(i, n, sumsP);\n                \n            for (int j = 0; j < sums.Length; j++) {\n                sums[j] = fruits[i][n1 - j] + PreviousMax(j, sumsP);\n            }\n\n            sumsP = sums;\n            // Console.WriteLine("sums: " + string.Join(", ", sumsP));\n        }\n\n        // Console.WriteLine(sumsP[0]);\n\n        total += sumsP[0];\n\n        sumsP = new int[0];\n        for (int i = 0; i < n1; i++) {           \n            int[] sums = GetArray(i, n, sumsP);\n                \n            for (int j = 0; j < sums.Length; j++) {\n                sums[j] = fruits[n1 - j][i] + PreviousMax(j, sumsP);\n            }\n\n            sumsP = sums;\n            // Console.WriteLine("sums: " + string.Join(", ", sumsP));\n        }\n\n        // Console.WriteLine(sumsP[0]);\n\n        total += sumsP[0];\n\n        return total;\n    }\n\n    private int[] GetArray(int i, int n, int[] sumsP) {\n        int nh = n / 2;\n        int nm = -1;\n        if (n % 2 == 1) nm = nh;\n\n        int[] sums;\n        if (i < nh) {\n            sums = new int[sumsP.Length + 1];\n        } else if (i == nm) {\n            sums = new int[sumsP.Length];\n        } else {\n            sums = new int[sumsP.Length - 1];\n        }\n\n        return sums;\n    }\n\n    private int PreviousMax(int j, int[] sumsP) {\n        List<int> p = new();\n        \n        if (j > 0) {\n            p.Add(sumsP[j - 1]);\n        }\n\n        if (j < sumsP.Length) {\n            p.Add(sumsP[j]);\n        }\n\n        if (j + 1 < sumsP.Length) {\n            p.Add(sumsP[j + 1]);\n        }\n\n        if (p.Any()) {\n            return p.Max();\n        }\n\n        return 0;\n    }\n}\n```
['Dynamic Programming', 'C#']