Coding interview 的 Dynamic programming cheatsheet

Introduction

Dynamic Programming（DP）通常用于优化问题。提升 DP 的唯一方法是大量练习，需要一定练习量才能更快识别问题是否可用 DP 解决。

Learning resources

• Demystifying Dynamic Programming
• Dynamic Programming – 7 Steps to Solve any DP Interview Problem
• Less Repetition, More Dynamic Programming, basecs
• Dynamic Programming, James Aspnes, Yale University

Techniques

并非所有情况都需要把完整 DP table 放到内存里，很多时候只需要最后两个值或矩阵的最后两行即可。

Essential questions

这些是该 topic 必练题。

• Climbing Stairs
• Coin Change
• House Robber
• Longest Increasing Subsequence

Recommended practice questions

这些是在掌握基础后推荐练习的题目。

• 0/1 Knapsack or Partition Equal Subset Sum
• Longest Common Subsequence
• Word Break Problem
• Combination Sum
• House Robber II
• Decode Ways
• Unique Paths
• Jump Game

Recommended courses

Grokking Dynamic Programming Patterns for Coding Interviews

Brought to you by the same folks behind the famous "Grokking the Coding Interview", this is one of the rare few courses focused on helping you get better at Dynamic Programming questions. If you are interviewing for companies who are famous for asking Dynamic Programming questions (-cough- Google -cough-), this course should be helpful.