Projeto Euler31: Entendendo a solução do programa

Question

Estou tentando entender uma solução para Projeto Euler #31 Eu encontrei nos fóruns.

O problema é que recebemos moedas com os seguintes valores:

coins=[1,2,5,10,20,50,100,200]

Temos a tarefa de gerar todas as maneiras possíveis de atingir 200. Por exemplo, 10*10+100 = 200 seria uma maneira possível.

1. Pergunta 2: Como o código abaixo funciona! Parece muito elegante, simples e direto em comparação com a minha abordagem e é muito mais rápido.

Enquanto eu estava navegando nos fóruns, encontrei esta solução:

p_list = [1, 2, 5, 10, 20, 50, 100, 200]
case_num = [1] + [0] * 200
for i in p_list:
    for j in range(1, 201):
        if i <= j:
            case_num[j] += case_num[j-i]
print case_num[200]

A primeira linha é apenas a lista dos valores da moeda. A segunda linha está criando uma matriz com 1 seguido por 200 0. Mas as próximas quatro linhas me deixaram confuso. Eu acho que está aumentando o número de maneiras possíveis da matriz, então Case_num [200] dará a última entrada na lista, mas não tenho idéia de como funciona.

Answer 1

Esta é uma solução muito boa, como você disse. O código se baseia em si mesmo através de cada iteração de 1-200 com cada denominação da moeda.

A matriz case_num consiste inicialmente em [1, 0, 0, 0, 0, 0 ... 0, 0, 0

O que esses números (além do 1 1) significam são quantas maneiras você pode aumentar o total fornecido (representado pelo índice do número) usando as moedas na lista de P_List que você já foi iterado até agora.

A primeira moeda em P_list é 1. Portanto, se 1 puder caber dentro do índice, você assume o valor no índice anterior e adicione -o ao seu índice atual. Isso funciona porque se houver 5 maneiras conhecidas de chegar a 25 e você acabou de encontrar moedas do tamanho 1, também haverá 5 maneiras de chegar a 26. [Cada uma das 5 maneiras anteriores de chegar a 25] + uma 1 moeda .

Então, depois de realizar com 1, você acabará com [1, 1, 1, 1, 1 ... 1, 1

Agora você sobe em moedas. Desta vez, você está usando uma moeda de 2. Vamos percorrer o processo mais 1 tempo. Se 2 for menor que o índice, você adiciona o número de maneiras de chegar ao índice anterior ao seu índice atual.

Por exemplo, 2 não se encaixa no índice 1, mas se encaixa no índice 2. Então você acabou de criar uma nova maneira de chegar a 2 a partir de 0, para que você tome todas as maneiras pelas quais você pode chegar ao 0 e adicioná -los ao seu índice atual. No índice 27, 2 se encaixam no índice para que você tome o número de maneiras de chegar a 25 e adicioná -los a 27 porque agora você tem (todas essas maneiras de chegar a 25 + uma moeda de 2) + (todas as maneiras de Você tinha que chegar a 27 antes de saber que tinha moedas do tamanho 2).

Então, depois de realizar com 2, você acabará com [1, 1, 2, 2, 3, 3, 4, 4 ...

Se você ainda está tendo problemas, pode valer a pena tentar passar por todo o programa (talvez em um total reduzido como 50 em vez de 200).