не смог доказать требования к динамическому программированию

Question

Я не могу доказать оптимальную субструктуру и перекрывающееся свойство подзадачи для задачи в link. Точная проблема со мной в том, что даже после понимания стандартных проблем dp я сталкиваюсь с проблемой при решении более новых проблем. Иногда я не могу найти подзадачи решений, и иногда я не могу доказать правильность моего подхода к проблеме. :

Answer 1

Учтите, что общее количество, которое у вас есть, когда вы доберетесь до кирпичного номера n, не повлияет на вашу стратегию; другими словами, оптимальный путь оттуда не зависит от того, как вы туда попали (окончательный счет зависит от него, потому что зависит от вашего текущего балла, но оптимальный путь не делает: вам просто нужно захватить столько, сколько вы можете с этого момента так или иначе).

Кроме того, учитывая, что противник собирается взять как можно больше тоже формула становится просто:

best of 
    worst of 
     me taking 1 and opponent taking 1 
     me taking 1 and opponent taking 2 
     me taking 1 and opponent taking 3 
    worst of 
     me taking 2 and opponent taking 1 
     me taking 2 and opponent taking 2 
     me taking 2 and opponent taking 3 
    worst of 
     me taking 3 and opponent taking 1 
     me taking 3 and opponent taking 2 
     me taking 3 and opponent taking 3 

так есть 9 возможностей для проверки и каждый из них будет игра со строго меньшим количеством кирпичей, которые могут решаются независимо (это ключевой момент для использования подхода с динамическим программированием) по указанной выше причине.