【LeetCode】Dynamic Programming I

今天依然手动 redirect 【Day 5】逻辑时间与广播
反正网路上讲 dp 的多的是，dp写得比我好得多的是～

初学者最大的敌人？

个人情感上，其实是很喜欢 DP 的，
我觉得 DP 是一个「解决好多原来好像无从下手的问题」的思路。
还记得第一次接触 DP，
好像是演算法课上的背包问题吧，
我就觉得这好实用啊，怎麽有人那麽聪明！

时至今日，几个月前开始写 Leetcode，
再次碰到 dp 是 97. Interleaving String，
那时我对於 dp 的印象几乎是 0 了ＸＤ
感谢当时的朋友非常耐心的划出了二维表格，
并一步一步解释给我听，
最後好不容易听懂了，又因为 coding 技能还没上来，
对於 matrix 的操作不熟，因此花了两小时才写出来..

最近读书会的朋友也提了一题 518. Coin Change 2，
说他努力看懂了，却想不出怎麽建构这样的思路。
这题算是背包问题的变化题，
而身为资管系的他连背包问题都没有学过，
难以 get 到我想也是情有可原～

对於很多 dp 初学者来说，
第一步是要先发现这件事情可能可以用 DP 做，
第二步是如何定义 dp 阵列，以及前一项和後一项的转换式，
第三步则是优化空间复杂度。

而 dp 问题我现在也没有很熟练，
太千变万化了，只能多做累积经验。
而或许对於初学者来说，
最重要的不是练好 dp，而是先将其他基础资料结构和更常用的演算法学好学扎实。
如果是 new grad，我目前还没碰到现场考 dp 的公司，顶多是前测。

DP 与其他演算法

DP 主要有两个性质：

• Optimal Substructure
  如果可以根据子问题的最优解构造最优解，
  则称该问题具有最优子结构

Greedy 演算法也有 Optimal Substructure，
目的是利用局部最佳解来获得全域最佳解，
而这样的做法常常需要数学证明。

• Overlapping Sub-Problems
  如果没有重复的问题，就没有记起来的必要，
  因此就会采用 Divide and Conquer。
  例如 merge sort, quicksort

DP 问题的技巧

首先要把问题用数学表达，
看看有哪些参数？
透过这些参数思考，该怎麽样去分解子问题，该怎麽样写出关系式？
DP 通常有两种形式：

1. Bottom up
2. Top down + 递回（memoization）
   通常我写 dp 都是 bottom up，一步一步建立上去。
   top down + 递回比较不是我认知的 dp，
   我会归类为 memoization。