Iterative DP | Easy To Understand
Intuition\nPrecompute the minimum number of changes for all the substrings to be pallindrome.\n\n# Approach\n1. Precompute the minimum number of changes for all
# Intuition\nPrecompute the minimum number of changes for all the substrings to be pallindrome.\n\n# Approach\n1. Precompute the minimum number of changes for all the substrings to be pallindrome. This can be done in $$O(n^2)$$.\n2. For each index \'r\', find the minimum changes to be applied till \'r\' for all values of \'k\'. This can be done in $$O(k*n^2)$$.\n3.  The transition would look like,\n$$minChanges(kk, r) = min(minChanges(kk-1, l-1)+changesFor(l, r)), for 0 <= l, r <= idx, 0 <= kk <= k.$$\n\n# Complexity\n- Time complexity:\n$$O(k*n^2)$$\n\n- Space complexity:\n$$O(k*n)$$\n\n# Code\n```\nclass Solution {\npublic:\n    int palindromePartition(string s, int k) {\n        int n = s.size() ;\n        int changes[n][n] ;\n        for(int l = n-1; l >= 0; --l)\n        {\n            for(int r = l; r < n; ++r)\n            {\n                if(l == r)\n                    changes[l][r] = 0 ;\n                else if(l+1 == r)\n                    changes[l][r] = (s[l] != s[r]) ;\n                else\n                    changes[l][r] = changes[l+1][r-1]+(s[l] != s[r]) ;\n            }\n        }\n        vector<vector<int>> dp(k, vector<int>(n, INT_MAX)) ;\n        for(int r = 0; r < n; r++)\n            dp[0][r] = min(changes[0][r], dp[0][r]) ;\n        for(int kk = 1; kk < k; ++kk)\n            for(int l = n-1; l >= kk; --l)\n                for(int r = l; r < n; r++)\n                    dp[kk][r] = min(dp[kk][r], dp[kk-1][l-1]+changes[l][r]) ;\n\n        return dp[k-1][n-1] ;\n    }\n};\n```
['Dynamic Programming', 'C++']