<commit_before>
# 1-D
1. [Decode Ways](https://leetcode.com/problems/decode-ways/)
2. [Word Break](https://leetcode.com/problems/word-break/)
3. [Sentence Screen Fitting](https://leetcode.com/problems/sentence-screen-fitting/)

[Decode Ways](https://leetcode.com/problems/decode-ways/) and [Word Break](https://leetcode.com/problems/word-break/) are similar, both are to decode.

Both divide the problem into n subproblems. The difference is that, for each subproblem, _Decode Ways_ takes constant time, while _Word Break_ needs linear time.

[Sentence Screen Fitting](https://leetcode.com/problems/sentence-screen-fitting/) has constrains that the word length won't exceed 10 and total words in the sentence won't exceed 100, so we can concat words into one sentence at firest. See [solution](https://leetcode.com/problems/sentence-screen-fitting/discuss/90845/21ms-18-lines-Java-solution).


# 2-D
1. [Edit Distance](https://leetcode.com/problems/edit-distance/)
<commit_msg>Update DynamicProgramming.md<commit_after>
# 1-D
1. [Decode Ways](https://leetcode.com/problems/decode-ways/)
2. [Word Break](https://leetcode.com/problems/word-break/)
3. [Sentence Screen Fitting](https://leetcode.com/problems/sentence-screen-fitting/)
4. [House Robber](https://leetcode.com/problems/house-robber/)
5. [House Robber II](https://leetcode.com/problems/house-robber-ii/)

[Decode Ways](https://leetcode.com/problems/decode-ways/) and [Word Break](https://leetcode.com/problems/word-break/) are similar, both are to decode.

Both divide the problem into n subproblems. The difference is that, for each subproblem, _Decode Ways_ takes constant time, while _Word Break_ needs linear time.

[Sentence Screen Fitting](https://leetcode.com/problems/sentence-screen-fitting/) has constrains that the word length won't exceed 10 and total words in the sentence won't exceed 100, so we can concat words into one sentence at firest. See [solution](https://leetcode.com/problems/sentence-screen-fitting/discuss/90845/21ms-18-lines-Java-solution).

In order for DP to work, the subproblem dependency should be acyclic, otherwise there will be
infinte loops. [House Robber II](https://leetcode.com/problems/house-robber-ii/) looks like cyclic, however it can be easily tranformed to [House Robber](https://leetcode.com/problems/house-robber/).

# 2-D
1. [Edit Distance](https://leetcode.com/problems/edit-distance/)

{'fraction_non_alphanumeric': 0.13110647181628393, 'fraction_numerical': 0.01753653444676409, 'mean_word_length': 4.801452784503632, 'pattern_counts': {'":': 0, '<': 3, '<?xml version=': 0, '>': 3, 'https://': 20, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '354795', 'n_tokens_mistral': 832, 'n_tokens_neox': 740, 'n_words': 211}