ARTS是什么？
Algorithm：每周至少做一个leetcode的算法题；
Review：阅读并点评至少一篇英文技术文章；
Tip：学习至少一个技术技巧；
Share：分享一篇有观点和思考的技术文章。
Algorithm
LC 1335. Minimum Difficulty of a Job Schedule
题目解析：
题目给定一个数组和一个整数，数组表示的是每个工作的难度，整数表示的是天数。每天都必须至少完成一个工作，并且工作之间有依赖关系，在完成第 i 个工作前，第 0 到第 i - 1 的工作都需要完成，每天的难度计算是算当天完成的最难的那个工作，求在这些天安排完成所有工作的最小难度值。
首先看到 最小值，以及这其中的依赖关系，我们就可以从动态规划的方向去思考，我们还是按照套路来分析一下：
-
问题拆解
最后我们必须要把 n 个工作安排到 d 天，因为有依赖关系的存在，其实可以看成每天安排一个区间的工作（子数组）。因此，抛开题目的背景，其实这道题目等同于让我们把一个数组分成 d 份，然后把每份的最大值加起来，求这个最大值和的最小值。
有了上面这些认识后，我们再来看如何拆解问题，当我们求 d 天的总难度的时候，我们需要看前 d - 1 天的总难度，也就是说前 d - 1 天分配工作的情况决定了第 d 天的情况。每天至少完成 1 个工作，无上限。也就说每天都可以分配 1 ~ n - d 件工作，这样我们就可以得到一个搜索树：
第 1 天 [0,0] or [0,1] or ... [0,...n-d] | | | 第 2 天 [1,1]... [2,2]... [n-d+1,n-d+1] ... ...基本上，搜索结构一出来，问题就算拆解完毕。
-
状态定义
根据上面的问题拆解，我们可以得知状态中需要表示两个信息，一个是天数，另外一个是工作，前者很好表示，后者的话其实是一个区间段，按理说区间段的起始和终止都需要表示，但是这里有个小 trick 就是，当天完成的第一个工作其实就是前一天完成的最后一个工作的下一个工作，因此我们只需要记录每天完成的最后一个工作即可。于是我们可以定义状态
dp[i][j]表示的是第 i 天完成的最后一份工作是 j 时的最小难度。 -
递推方程
有了上面的状态定义，递推方程应该不难得出：
dp[i][j] = Math.min(dp[i - 1][k - 1] + MAX(k, j)), 其中 i <= k <= j你的状态定义决定了递推方程
-
实现
从递推方程可以看出，当前天的信息需要用到前一天的信息。为了保证计算过程数组访问不越界，我们需要提前初始化第 0 天的情况。时间复杂度方面可以从递推方程中得出：O(d * n * n)。
动态规划问题，主要的难点还是在问题拆解和状态定义上，掌握这个只能是多练，多思考，多总结，没有过多的技巧。
参考代码：
public int minDifficulty(int[] jobDifficulty, int d) {
if (jobDifficulty == null || jobDifficulty.length < d) {
return -1;
}
int n = jobDifficulty.length;
int[][] dp = new int[d][n];
// dp 状态数组记录的是最小值，这里进行状态数组初始化
for (int[] sub : dp) {
Arrays.fill(sub, Integer.MAX_VALUE);
}
dp[0][0] = jobDifficulty[0];
for (int i = 1; i < n; ++i) {
dp[0][i] = Math.max(dp[0][i - 1], jobDifficulty[i]);
}
for (int i = 1; i < d; ++i) {
for (int j = i; j < n; ++j) {
int curMax = jobDifficulty[j];
for (int k = j; k >= i; --k) {
curMax = Math.max(curMax, jobDifficulty[k]);
dp[i][j] = Math.min(dp[i][j], dp[i - 1][k - 1] + curMax);
}
}
}
return dp[d - 1][n - 1];
}
Review
How to prepare for competitive programming ?
这是一篇介绍如何准备算法程序竞赛的文章。不得不说当下很多公司招人都会考察面试者的解决实际问题的能力，而算法则是重点考察的一个方面。通过程序竞赛的训练，可以提升你的程序思维能力和反应力，另外由于软件行业从业者的日益增长，竞争开始慢慢变得激烈，很多公司开始使用难度比较大的偏竞赛类的题目作为面试题，因此程序竞赛的价值变得越来越大。那我们该如何通过竞赛这个渠道来提升自己呢？作者给了几个观点：
-
编程语言首选 C++
C++ 是程序竞赛的首选语言，程序竞赛讲究的是程序运行的速度，这方面只有 C++ 比较有优势。JAVA 在程序竞赛中往往不被接受。
-
确定属于你自己的代码风格
选择自己的代码风格遵循两个原则，一是要比较好实现，越简洁是越好的，这样竞赛的时候不会花费过多的时间在实现上，另外一点是方便查阅，这个主要是为了 debug 的时候代码比较清晰。代码竞赛时的代码风格主要是给自己看的，而且代码量都不会很大，因此这里不需要考虑变量命名、程序规范之类的东西，速度是第一要素。当然，这样的习惯不要带到工作或者是面试中，不然会影响的他人的评价。
-
扎实的基础是关键
这里作者特别强调我们需要去尝试接触难一点的题目，每做三道题目，你必须从其中的至少一道题目有所收获，不然的话，你就需要尝试去适当提升题目的难度，只有不断走出自己的舒适区，才会有成长。另外，作者还特别强调了动态规划的掌握，如果能够真正掌握动态规划，那在竞赛中会十分有优势。
-
训练用大脑 debug
平日里，我们总喜欢借助一些工具来帮助我们 debug，但是程序竞赛并不会给你这样的时间，因此你需要训练你发现问题，在脑袋中快速审阅代码，发现问题的能力，这个能力也是慢慢训练起来的。
不得不说，程序竞赛是一个需要花大量时间去准备的一个比赛。想要拿到好成绩，高时间的投入是必须的，因此，在校的学生会很有优势。当然，参加工作后我们也可以通过竞赛的题目来训练自己对程序的理解和编程思维能力的提升，按我自己的观点，虽然参加工作后没有大块的时间，但是我们可以把战线拉长，我们不以竞赛拿奖为目的，而是以学到真的知识为目的。同时，作者在文章中也说道，重要的还是反复，学过的东西如果不去做题来巩固知识点，那么很快就会忘记。因此，每周都有做算法题，然后试着去走出自己的舒适区，学学不同的算法知识，不用太快，慢慢地，相信思维能力会有从量变到质变的飞跃。
Tip
这次试着在阿里云 ubuntu 系统上架 NodeJS + MySQL，这里记录一下：
在 Ubuntu server 上安装 NodeJS & NPM：
$> sudo apt-get update
$> sudo apt-get install nodejs
$> sudo apt install nodejs-legacy
$> sudo apt-get install npm
$> curl -sL https://deb.nodesource.com/setup_10.x — Node.js 10 LTS "Dubnium" | sudo -E bash -
$> sudo apt-get install -y nodejs
在 Ubuntu server 上安装 MySQL：
$> sudo apt install mysql-server
感觉工具还是越少越好，不然经常会因为配置而纠结很久。
Share
今天就不再继续写文章了，分享一篇耗叔的文章。主要讲的是我们该以什么样的态度去学习，这里总结一下我认为的要点：
- 主动学习的效率会更高
- 需要践行深度学习
- 学习是为了找到藏在知识背后的东西
- 学习是为了改变自己的思考与思维方式，抛弃那些坏习惯
总之，学习是一生的事情，也是一件 “逆人性” 的事情，放弃的理由有千百个，坚持的理由只有一个，那就是让自己变得更加优秀，让自己以后有更多的选择。
