DP打卡日记

8月4号
第一题 LC 375

注意这个题和之前做过的一题很像（忘了是哪题了），就是要先把小的区间的dp值求出来，再求大的区间。所以先设定的区间的值，从小到大遍历。

Take n = 5 as an example
First guess could be 1 or 2 or 3 or 4 or 5

1: 1 + Max([1, 0], [2, 5])
2: 2 + Max([1, 1], [3, 5])
3: 3 + Max([1, 2], [4, 5])
4: 4 + Max([1, 3], [5, 5])
5: 5 + Max([1, 4], [6, 5])

If we pick a number x, we need to pay $x, and we need to choose the max side of x's two sides for the next guess.
We iterate through 1 to n to get a minimum.

dp[i][j] means the minimum value of guessing from i to j, the return value is dp[1][n]

第二题 LC 343 Integer break

// 错误1： dp[i] = Math.max(dp[i], Math.max(x * dp[i - x], x * (i - x)));
写成了  dp[i] = Math.max(dp[i], Math.max(x * dp[n - x], x * (i - x)));
debug 了十分钟，还以为思路错了，写代码注意啊，这种小bug有时候很难发现。

256. Paint House
这题locked了，在lintcode做的。
这个题有点意思，根据现在颜色，选之前的屋子dp值比较低的不同颜色来更新。

8月5号

第一题 Paint house 2
这个题是paint house 1 的加强版，并没有难多少，只是多一个循环而已。

第二题 Edit distance
这个题三个条件没有彻底理解清楚，导致状态转移方程搞错了。其实说到底，还是没有完全明白dp矩阵代表的物理意义。在Grandyang的博客找到一句话，深刻了理解了一下：当word1[i] == word2[j]时，dp[i][j] = dp[i - 1][j - 1]，其他情况时，dp[i][j]是其左，左上，上的三个值中的最小值加1，其实这里的左，上，和左上，分别对应的增加，删除，修改操作。

第三题，Interleaving String
97. Interleaving String

二刷

可以写出递归的解法，但是TLE。
我知道要用大DP解，但是我卡在一个地方：如何表达s1 和 s2 组合成 s3 ? dp[i][j][k] 吗？
难点一：原来是 dp[i][j] 代表s1 前i个字母 和s2前i个字母能否组成s3 前 (i + j)个字母
难点二：注意初始化 dp[i][0] 和 dp[0][i]