突然就刷不下去了，该怎么调适？

"半夜还会莫名一直哭"---楼主需要看一下医生，看有没有是抑郁带来的问题。

累了就歇几天，我之前刷太急一想到bfs dfs backtracking dp就想吐。
当时后面有重要面试也懒得刷。。。缓了几周现在好了。建议第一遍的时候不要刷hard。

刷leetcode可以先看看网上刷题攻略，先把leetcode的Explore->Learn下面些基本category刷完，那个就100多道题，然后自己看哪块需要补，也可以按照需要准备的公司的tag刷题，每天做做daily challenge，找个刷题小组

刷不下去的时候可以看看地里抖得包袱，还有哭诉没工作得惨状，马上精神就上来了。

如果只是 DP 把 LZ 整的这么闹心的话，LZ 不如停下来想一想，dp 的本质是什么。不知道 LZ 有没有看过/课上用过 CLRS，DP 那一张开篇词中对于一般 dp 问题和 divide-and-conquer 问题进行了一番对比：

“Dynamic programming, like the divide-and-conquer method, solves problems by combining the solutions to subproblems......divide-and-conquer algorithms partition the problem into disjoint subproblems, solve the subproblems recursively.....”
停下来想一想，我们是如何解决divide-and-conquer问题的？对每个子问题递归求解

“.....In this context, a divide-and-conquer algorithm does more work than necessary, repeatedly solving the common subsubproblems.”
这里很关键，对于 dp 问题，用 divide-and-conquer 的老办法行不行？行！但是慢，存在重复求解的情况。

好了，到这里猜也能猜到了，dp 做了什么？dp 对递归过程进行了优化，我们将重复子问题的解存在一个“table”里面，来减少重复求解的次数。

在这里我认为有很重要的一条主线：dp 是对递归过程的优化。我觉得对于我们这样的非天赋异禀得选手，我觉得在思考一道 dp 问题的时候，至少从暴力递归到 dp 这个过程是不应当跳过的

与之对应，CLRS 紧接着给了解决一般 dp 问题的三个 step：
1. Characterize the structure of an optimal solution.
2. Recursively define the value of an optimal solution.
3. Compute the value of an optimal solution, typically in a bottom-up fashion.
很抽象，但紧接着 CLRS 在第一个 rod cutting 问题里面就给出了从暴力递归到记忆化搜索再到 dp 的完整过程，建议 LZ 好好读一下。

下面我用一个例子过一遍这个过程，例子是 LC.322 Coin Change 经典背包问题。
我先给出 recursive 版本，这个应该是都能写得出来：

1. class Solution {
   
2.     public int coinChange(int[] coins, int amount) {
   
3.         int len = coins.length;
   
4.         if(amount == 0) {
   
5.             return 0;
   
6.         }
   
7.         
   
8.         return recursive(amount, len, coins);
   
9.     }
   
10.    
    
11.     private int recursive(int remain, int len, int [] coins) {
    
12.         if(remain == 0) {
    
13.             return 0;
    
14.         }
    
15.         
    
16.         int minCnt = Integer.MAX_VALUE;
    
17.         
    
18.         for(int coin : coins) {
    
19.             
    
20.             if(remain - coin < 0) continue;
    
21.             
    
22.             int subRes = recursive(remain - coin, len, coins);
    
23.             
    
24.             if(subRes >= 0 && subRes < minCnt) {
    
25.                 minCnt = subRes + 1;
    
26.             }
    
27.         }
    
28.         
    
29.         return minCnt == Integer.MAX_VALUE ? -1 : minCnt;
    
30.     }
    
31. }

复制代码

作为一个超时解，如何优化成 dp ？这里就涉及到 dp 中的“状态”和“状态转移方程”

状态怎么找？回看我们的 recursive body，有什么是能够区分两个不同的 recursive call 的呢？只有 function signature 里面的argument remain，remain 的值不一样，那么我们所处的状态就不一样。
dp 数组要多大？往下看 recursive body，一上来递归结束条件说

1. if(remain == 0)  return 0;

复制代码

在最初调用 recursive call 的时候，我们是这样写的

1. return recursive(amount, len, coins);

复制代码

那么，remain 的范围可以从 0 到 amount，左闭右闭区间。好了我们由此定义我们的 dp 数组

1. int [] dp = new int [amount + 1];

复制代码

dp 问题一般需要我们给一个 initial state，作为解决后续子问题的基础，这个其实也出现在 recursive body 当中了，就是 recursive 的结束条件

1. if(remain == 0) return 0;

复制代码

上面告诉我们，dp[0] = 0。为什么? 再次强调 remain 就是我们的“状态”

状态转移方程怎么找？其实不用找，我们都已经写在 recursive body 里面了，只需要把对应的 recursive call 换成 array indexing 就可以。原来 recursive body 当中最后的 return value 其实就是我们要的 dp的值。把 recursive body 改一下

1. int minCnt = Integer.MAX_VALUE;
   
2.             
   
3.             for(int coin : coins) {
   
4.     if(remain - coin < 0) continue;
   
5.                
   
6.     int subRes = dp[remain - coin]; // recursive call 改成 array indexing
   
7.                
   
8.     if(subRes >= 0 && subRes < minCnt) {
   
9.         minCnt = subRes + 1;
   
10.     }
    
11. }

复制代码

至此，我们可以丢掉我们的 recursive body 了，把上面的内容合在一起就是这样

1. class Solution {
   
2.     public int coinChange(int[] coins, int amount) {
   
3.         int len = coins.length;
   
4.         if(amount == 0) {
   
5.             return 0;
   
6.         }
   
7.         
   
8.         int [] dp = new int [amount + 1];
   
9.         
   
10.         dp[0] = 0;
    
11.         
    
12.         for(int remain = 1; remain <= amount; remain ++) {
    
13.             
    
14.             int minCnt = Integer.MAX_VALUE;
    
15.             
    
16.             for(int coin : coins) {
    
17.                  if(remain - coin < 0) continue;
    
18.                
    
19.                 int subRes = dp[remain - coin];
    
20.                
    
21.                 if(subRes >= 0 && subRes < minCnt) {
    
22.                     minCnt = subRes + 1;
    
23.                 }
    
24.             }
    
25.             
    
26.             dp[remain] = minCnt == Integer.MAX_VALUE ? -1 : minCnt;
    
27.         }
    
28.         
    
29.         return dp[amount];
    
30.     }
    
31. }

复制代码

dp 版本算是完成了(瘫。。。)


回顾一下，看看能不能找到一些通用的解法：
1. 先写出 recursive 版本
2. “状态” 是根据 recursive function signature 中会变化的 arguments 找到的，可能有一个、两个、三个，对应一维、二维、三维 dp
3. dp 数组定义多大要去看“状态” 的变化范围，主要就是 看第一次 recursive call 和 recursive call 的 termination condition
4. dp 数组初始状态是从 recursive call 的 termination condition 找到的
5. “状态转移方程” 是根据 recursive body 改写出来的，基本上就是把 recursive function call 换成 array indexing
6. 计算 dp 数组的时候是从左往右算还是从右往左 要看最后 return statement 中我们 return 的是0位置上的值还是最后一个值。也会有一些问题要我们再次遍历一遍 dp 数组找出满足条件的值

其他：
1. 这个办法能所有 dp 问题吗？不能，但是能解决很大一部分。
2. 为啥别人写出来的和这样写出来的不一样？bottom-up dp 和 top-down dp 思路不同代码也可能不同/有的问题可以进行“状态压缩”/也有的问题确实 tricky
3. 这样也太慢了吧。没错一开始是很慢，多练就快了，只要能写出 recursive 版本，我觉得改成 dp 可能用不了几分钟。练得多了其实不一定要完完整整写出 recursive 版本，大概脑子里过一下 recursive 版本是什么样，状态/状态转移方程什么的也就出来了。

dp本来就不好想 没啥可焦虑的，多找几个类型题目练一下就好了，真遇到不会的，再多练习也不好用，如果时间有限，该放弃就得放弃，不知道你一天几道题，我一天2-3道中等，2-3道简单。没思路就直接看答案，逼着自己做出来效率会很低，如果遇到题目太难，推荐刷几道easy调整心情，刷题这东西，心情最重要。
由于要工作，所以一天大概4道题
心情好就是3道中等
心情不好就1道
想偷懒2道
之后就是快乐的简单题时间
一般一天2小时左右

感觉和楼主有点像，心态有点崩，同刷了100多道题。硕士转专业，想到之前浪费的时间就觉得对不住父母砸的钱。我刷到烦的时候就起来做点别的事转移注意力，或者听听音乐蹦哒一会儿，调整调整心态，多想想刷题这条路上肯定不止我一个人这么丧，这不，我就看到了你的帖子…..还有，其实做不出来题挺正常的，想开点。加油！

pphuangyi 发表于 2021-9-7 11:26
我知道我这么说，可能楼主会觉得不靠谱，但是我也希望楼主能稍微考虑一下我说的。我觉得楼主可能需要和你一 ...

很谢谢您的建议，一点都不会不靠谱，相反地，我认为很实用。
我很认同你说的，可能是没有夥伴的缘故，因为我比较怕生，很多群要讨论的都不好意思参与，觉得自己程度差，反而拖累人家。又怕自己心情不稳定没跟上进度，给群里的小夥伴添麻烦，我会再找找合适的对象一起练习，希望会有用，谢谢

nightshade 发表于 2021-9-8 01:09
如果只是 DP 把 LZ 整的这么闹心的话，LZ 不如停下来想一想，dp 的本质是什么。不知道 LZ 有没有看过/课上 ...

nightshade您好，
非常谢谢您这么热心地为我写了详尽的解释，
说来惭愧，这两天我在家大哭了几场，也打了几个视讯电话给以前比较好的朋友聊天，
我之前有些惧怕看到dp，现在还有一些些，但我有再努力想重拾勇气了，等几天好转后定会来拜读您这篇大作。到时候如果有看不懂再提问，真的非常感谢。

大家的留言我都一一看过了，很谢谢大家的建议，还有分享的课程影片，或是建议我去看心理谘商的。
这两天我在家大哭了好几回，平常压抑有点久了，还特地找了些催泪作品来看抒发情绪。
也久违地跟一些朋友透过视讯连络上聊天。

很多人都建议我心态改变调整一下，我会想办法努力的。
我觉得自己看多了别人的励志故事，想说服自己更坚强总能熬出天，就总是把苦吞了下去，怕忧郁的自己做不好事情又给大家带来麻烦，就假装自己不忧郁，结果终在一个情绪濒临崩溃的点爆炸了。
老实说我哭了两天也不觉得自己能这么快就调适好心情，感觉今天躺在床上又会不自觉掉下泪来，但还是谢谢大家的留言让我觉得很温暖，虽然只是在地里的一个擦身而过，看到你们的留言让我觉得自己又多了一点勇气。

真的很谢谢大家不吝分享。
我会想办法赶快振作起来。