DP打卡日记

前300道题基本刷完了，现在开始第二轮，刷专题。动态规划一直是薄弱项，之前上算法课期末考试一道20分的dp大题没做出来，最后成绩是A-，痛失CS全A战绩。今日开始打卡dp题。每天两道吧，最好是白板，没有白班就笔记本写题吧。

今天第一题：LC64，min path sum

错误1：三目运算符没有加括号，导致bug。条件运算符优先级远低于+，以后要注意。

8月1号
第一题：
LC 312 Burst Balloons

这题和以前遇到的矩阵乘法的题基本是一样的。算法课上讲过的，不过我还是忘了，还是看的大神的解释才明白的。惭愧。

1. class Solution {
   
2.     public int maxCoins(int[] nums) {
   
3.         int n = nums.length;
   
4.         if (n == 0) {
   
5.             return 0;
   
6.         }
   
7.         int[] A = new int[n + 2];
   
8.         A[0] = A[n + 1] = 1;
   
9.         for (int i = 1; i <= n; ++i) {
   
10.             A[i] = nums[i - 1];
    
11.         }
    
12.         
    
13.         int[][] dp = new int[n + 2][n + 2];
    
14. 
    
15.         for (int len = 1; len <= n; ++len) {
    
16.             for (int i = 1; i <= n - len + 1; ++i) {
    
17.                 int j = i + len - 1;
    
18.                 for (int k = i; k <= j; ++k) {
    
19.                     dp[i][j] = Math.max(dp[i][j], dp[i][k - 1] + dp[k + 1][j] + A[i - 1] * A[k] * A[j + 1]);
    
20.                 }
    
21.             }
    
22.         }
    
23.         
    
24.         return dp[1][n];
    
25.     }
    
26. }

复制代码

7月30日 第一题：LC 309,Best Time to Buy and Sell Stock with Cooldown

这题我做不出来，看的花花的视频。因为没有时间在白板上写，直接写的code

1. class Solution {
   
2.     public int maxProfit(int[] prices) {
   
3.         int n = prices.length;
   
4.         int[] hold = new int[n + 1];
   
5.         int[] sold = new int[n + 1];
   
6.         int[] rest = new int[n + 1];
   
7.         hold[0] = Integer.MIN_VALUE;
   
8.         for (int i = 0; i < n; i++) {
   
9.             hold[i + 1] = Math.max(hold[i], rest[i] - prices[i]);
   
10.             rest[i + 1] = Math.max(rest[i], sold[i]);
    
11.             sold[i + 1] = Math.max(sold[i], hold[i] + prices[i]);
    
12.         }
    
13.         return Math.max(sold[n], rest[n]);
    
14.     }
    
15. }

复制代码

难点：
分析三个状态之间的转换。根据转换写出状态转移方程。

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值比较低的不同颜色来更新。

7月29日 第二题：LC 392

错误1：状态转移方程搞错了。应该是s[i-1] != t[j-1] , dp[i][j] = dp[i][j - 1]; s[i -1] == t[j - 1], dp[i][j] = dp[i - 1][j - 1]

另外，这个题有个更牛更简单的方法，就是用双指针，当两个字母相等的时候，两个指针都增加，如果不相等，只增加t指针，最后检查s指针是否到了结尾即可。

8月1号第二题LC 62 Unique Paths
2-D DP array -> reduced to 1-D DP array
dp[j] = dp[j] + dp[j - 1];

8月1号第三题 LC 63 Unique Paths II
2-D DP array

8月1号第四题 LC 70 Climbing Stairs
这题比较简单，可以不用一维数组，用O(1)的空间就可以做。

除了lc，有兴趣其实可以去找找usaco的题目，难度高一点同时也非常锻炼写码能力

加油 顺便也求加分

8月2号

第一题：LC 279，Perfect Squares

最多的情况是 n =  n 个 1 相加，现在要求最少的情况，我们假设 n 是由 若干个 完全平方数组成，如下
n = a ^ 2 + b ^ 2 + c ^ 2 + … + x ^ 2;
假设我们已经知道了n - x^2 的值，那么我们就知道了 n， 加1就行
dp[i] = the least number of perfect square numbers which sum to n.
所以 dp[n] = min (dp[n - x * x]) for all x

第二题：LC139, Word Break

第二刷的时候还是和第一遍一样，TLE

其实发现最后的改动只是加了两行代码：
        if (map.containsKey(s)) {
            return map.get(s);
        }
想来好笑，如果不直接查询map，那这个map的作用根本没有体现出来啊，递归的时候一定要尽量在开始的时候把条件写清楚，在一开始的时候就阻止递归的调用。

另外，也感慨一下，刷题刷的多是一方面，刷得透也很重要。