💥💥100% beats runtime and memory [EXPLAINED]
Intuition\nWe need to split a string into a certain number of parts where each part is a palindrome. To minimize the number of changes needed to make each part 
# Intuition\nWe need to split a string into a certain number of parts where each part is a palindrome. To minimize the number of changes needed to make each part a palindrome, we should find the best way to divide the string into these palindromic segments with the least modifications.\n\n\n# Approach\nCalculate Costs: First, figure out how many changes are needed to make any substring a palindrome. This is done by comparing characters from both ends of the substring and counting mismatches.\n\n\nDynamic Programming (DP): Use a table to keep track of the minimum changes needed to divide the string into palindromic parts. For each possible partition, update the table with the least number of changes.\n\n# Complexity\n- Time complexity:\nO(n2 x k), where n is the length of the string. This includes time to calculate palindrome costs (O(n2))and filling the DP table O(n2 x k).\n\n- Space complexity:\nO(n2) for storing the costs and DP values.\n\n# Code\n```csharp []\nclass Solution {\n    public int PalindromePartition(string s, int k) {\n        int n = s.Length;\n\n        // 1. Precompute the cost to make each substring a palindrome\n        int[,] cost = new int[n, n];\n        \n        // Initialize cost array\n        for (int len = 2; len <= n; len++) {\n            for (int i = 0; i + len - 1 < n; i++) {\n                int j = i + len - 1;\n                cost[i, j] = cost[i + 1, j - 1] + (s[i] == s[j] ? 0 : 1);\n            }\n        }\n\n        // 2. DP table: dp[i][j] represents minimum changes to split first i characters into j palindromes\n        int[,] dp = new int[n + 1, k + 1];\n\n        // Initialize DP table with a large number (e.g., 100)\n        for (int i = 0; i <= n; i++) {\n            for (int j = 0; j <= k; j++) {\n                dp[i, j] = 100;  // A large number as initial value\n            }\n        }\n        \n        dp[0, 0] = 0;  // Base case: 0 characters and 0 palindromes need 0 changes\n\n        // 3. Fill the DP table\n        for (int i = 1; i <= n; i++) {  // Process first i characters\n            for (int j = 1; j <= k; j++) {  // Process into j palindromic substrings\n                for (int p = 0; p < i; p++) {  // Check all possible splits\n                    // Update DP value with the minimum changes required\n                    dp[i, j] = Math.Min(dp[i, j], dp[p, j - 1] + cost[p, i - 1]);\n                }\n            }\n        }\n\n        // 4. Return the result: Minimum changes to split the entire string into k palindromic substrings\n        return dp[n, k];\n    }\n}\n\n```
['C#']