[Python] Top Down DP
\n\nApproach: (click to show)\n\nIterate over the columns from left to right.\nFor each column (i) there are 2 choices.\n1. Delete the column.\n2. Keep the colu
<details>\n\n<summary><b>Approach:</b> (click to show)</summary>\n\nIterate over the columns from left to right.\nFor each column (i) there are 2 choices.\n1. Delete the column.\n2. Keep the column.\n\n**It is always okay to choose the first option.**\nAdd 1 every time a column is deleted - to keep track of how many columns have been deleted:  ```best = 1 + helper(i+1, bound)```\n\n<br>\n\n**It is not always okay to choose the second option.**\nHere are the rules that must be followed when choosing to keep a column.\n1. The first column **must be in sorted order.**\n```seeds``` contains all of the columns that are in sorted order.  \n2. The second, third, ..., N<sup>th</sup> column must not break the lexicographic order.\n\n\nTo make sure we do not break the second rule, we need to remember 1 thing.\n**Remember which rows exactly match the row above them so far.**\n\n<br>\n\nThis is done with the tuple ```bound```.  (A tuple is used because tuples can be cached)\n```bound``` is the length of A ~ so it has 1 element for each row in A.\n```bound[j] == True``` it means that the current row exactly matches the row above it.\n**When row[j] is bound, then the character at row[j][i] must be greater than or equal to the character at row[j-1][i].**  (the character directly above it)\n\n<br>\n\nIf **any** character in a column is both bound **and** less than the character directly above it, then the column **must** be deleted.\nAfter iterating over all of the columns (```i == len(cols)```) then return 0 because there are no more columns to keep or delete.  \nThe answer will be the path of choices that yields the lowest number of deletions.  \n\n</details>\n\n<br>\n\n```python\ndef minDeletionSize(self, A: List[str]) -> int:\n\n\trows = [list(string) for string in A]\n\tcols = list(zip(*rows))\n\n\t# make a list of the columns that are in sorted order\n\tseeds = set()\n\tfor i in range(len(cols)):\n\t\tif list(cols[i]) == sorted(cols[i]):\n\t\t\tseeds.add(i)\n\n\t@functools.lru_cache(None)\n\tdef helper(i, bound):\n\n\t\tif i == len(cols):\n\t\t\treturn 0\n\n\t\t# delete column i\n\t\tbest = 1 + helper(i+1, bound)\n\n\t\t# use column i as the first column (must be a sorted column)\n\t\tif not bound and i in seeds:\n\t\t\tbest = min(best, helper(i+1, tuple([False] + [rows[j-1][i] == rows[j][i] for j in range(1, len(rows))])))\n\n\t\t# keep column i (all characters must be either 1. free or 2. greater than or equal to the character directly above it)\n\t\telif bound:\n\t\t\tif all(not bound[j] or rows[j][i] >= rows[j-1][i] for j in range(len(rows))):\n\t\t\t\tbest = min(best, helper(i+1, tuple([False] + [bound[j] and rows[j][i] == rows[j-1][i] for j in range(1, len(rows))])))\n\n\t\treturn best\n\n\treturn helper(0, False)\n```
[]