<jupyter_start><jupyter_text>Count the ways...Given an N x M matrix of zeros... write a function to count the number of ways to get from the top-left corner to the bottom-right corner... you can only move right or down. Ex: 2x2 --> returns 2Ex: 5x5 --> returns 70This is clearly a dynamic programming question in disguise. Most questions where the naive solution is recursive in some ways are dynamic programming questions. For instance, it's clear that the 5x5 matrix at some point becomes a 2x2 matrix problem (as you move your way through). In fact, this reminds me of that staircase question, too.<jupyter_code>def num_ways(n,m):
    if n == 1 or m ==1: 
        return 1
    return num_ways(n-1, m) + num_ways(n, m-1)
# this creates a lot of repeated subcomputations. 
# hence, we should use dynamic programming

def num_ways(n,m): 
    A = [[0 for _ in range(m)] for _ in range(n)]
    for i in range(n): 
        A[i][0] = 1
    for j in range(m): 
        A[0][j] = 1
    for i in range(1,n): 
        for j in range(1,m): 
            A[i][j] = A[i-1][j] + A[i][j-1]
    return A[-1][-1] 
# this runs in O(N*M) time and space<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.10738831615120274, 'fraction_numerical': 0.023195876288659795, 'mean_word_length': 3.0311418685121105, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 7, 'https://': 0, '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}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '418210', 'license': 'MIT', 'n_tokens_mistral': 401, 'n_tokens_neox': 376, 'n_words': 167, 'path': 'Daily/Move Right Down.ipynb', 'repo_name': 'jasonyum/python_go', 'size': '1164'}