在职打卡学习

开个帖子打卡，刷题+学习，在职可支配时间不多，精力有限，希望能坚持每天进步一点

07/03/2020 第4天，明天继续！
就做了一题 375 Guess Number Higher or Lower，Py + Java，想了好久才完全理解代码，备注了一些思考。。。

整体思路是dp[l][r] = min(dp[l][r], max(dp[l][k - 1], dp[k + 1][r])) 对k做循环  
1. 一直不理解为什么这个DP不需要初始化。其实创建数组就已经初始化了，dp[k][k] = 0的
2. 第三层循环为什么不遍历k = start + len - 1的情况，因为一定不会选最后一个数，比如[1, 2]，真实是1，选1开销最小，真实是2，选1还是开销最小！所以没必要遍历最后一个数
3. DP方程中max很好理解，为了保证一定能赢，但最后为什么要min，因为其实k是你的选择，最后是遍历完k，才去选择的，所以min是在找最优的那一条路径

class Solution {
    public int getMoneyAmount(int n) {
        int[][] dp = new int[n + 1][n + 1];
        
        for(int len = 2; len <= n; len ++) {
            for (int start = 1; start <= n - len + 1; start ++) {
                dp[start][start + len - 1] = Integer.MAX_VALUE;
                for (int k = start; k < start + len - 1; k ++) {
                    int temp = Math.max(dp[start][k - 1], dp[k + 1][start + len - 1]);
                    dp[start][start + len - 1] = Math.min(dp[start][start + len - 1], temp + k);
                }
            }
        }

        return dp[1][n];
    }
}

07/04/2020 第5天，明天继续！
DP: 312, 322 Py + Java，312 Leetcode Java bug，不能用Integer.MAX_VALUE初始化，需要估计一下最大值，自己在IntelliJ上用MAX_VALUE初始化并没有问题

312这题和word break思路差不多
322一开始用的DFS，超时了，DP的解法和昨天的Guess Number Higher or Lower II思路差不多，但是k这里是最后爆炸的气球，先搞定左边和右边，再搞定k这个气球，375 这题则是先搞定k，再处理左右边。之所以这里k是最后做，因为只有这样才能保证left和right相互独立

07/11/2020 第9天，明天继续！
上班果然很难坚持每天学习，事情多就断了。。。

DP: 174, 221 Py
174: 开始想到DFS思路，但是超时，改用DP，比较难想到的点是dp[i][j]的含义，表示从此点出发到终点需要多少生命值，方程也比较难想dp[i][j] = max(1, min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j])
221：这题同样是dp[i][j]的含义，一开始想法是表示面积，但是发现这样构造方程比较困难，所以改成表示边长，方程就简单了很多

06/30/2020 第一天，明天继续！

DP: 70, 72 Python + Java
DL: section 7

07/01/2020 第2天，明天继续！

DP: 63, 120 Python + Java
DL: section 8

07/02/2020 第3天，明天继续！

DP: 279, 139 Python + Java 279看了答案才有思路，139用DFS做超时了，DP方法和139有些类似
279 DP思路 dp[j] = min(dp[j], dp[j - i*i] + 1)
139 DP思路 dp[i] = dp[0:k] && dp[k:i]

07/05/2020 第6天，明天继续！
DP: 256, 265 Py

256 思路就是2维dp，每个元素记录当前的最小值
265 用了同样的思路，稍微变形，感觉还可以再优化一下，明天再review下这题。。。

补打卡 07/06/2020 第7天，明天继续！
DP: 64 Py 比较简单，和找出口那道题很相似

07/07/2020 第8天，明天继续！
DP: 72, 97 Py
72题分析题目比较重要，比较最后一个字母，相同，则同-1，不同则有3种变换，求最小再 + 1，初始化每个字符串分别和空串比较，也是为什么dp矩阵式n + 1, m+1维
97题先手画一下dp矩阵，行为str1，列为str2，类似找一个连通的路径，每走一步，看一下上一步的两种可能，再和str3作比较，思路想到了，感觉没有上一题难