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

楼主资质愚钝，刷题刷得很慢，常常DP看人家分享解答老半天也不知道他怎麽想出来的，只好抄起来，背起来，但题目换几个字眼，或稍微follow-up一下，就见真章解不出来了。

本来觉得勤终能补拙，总能拨云见日，慢慢读没关係，死记没关係，

从几个月前开始找工作，刷这麽久到现在也才刷一百多题左右，在各位大大眼裡肯定是见笑，肯定也觉得我怎麽这样就嫌累了。
但真的是这样子，我也不知道怎回事，就像有时候你也知道自己在偷懒却死要拖延，然后晚了再来满身的自责感。

不停地被想要的工作拒，心情好像卡住了，有天起来打开书，再也看不下内容。
想着是不是随便应徵个工作就好呢？但又愧对孕育我的父母亲，把我栽培大了，砸了一堆钱读书了，却随便混了个工作，无法尽孝...

我最近仍然强迫自己出门，带着电脑到了图书馆坐坐，却写不了几题，一直恍神，我想我是倦了，但我又知道我不能倦...
这可怎好呢？有没有人有遇过相同状况能提点的呢？

我最近越睡越糟，半夜还会莫名一直哭，每个夜晚都在懊恼自己刷不了题，很糟糕，很窝囊，但白天醒来到了图书馆又是这样子。

想说逛逛地裡，找找别人读书的经验或是其他还没面的公司，结果米个不小心都用到不足了...也还没振作起来
找不回动力，觉得自己真窝囊啊。

有没有相同经验的大老能指点个呢？
我知道自己该振作该出门读书，也去了，也读了，但字读不进心裡啊...

如果只是 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 版本是什么样，状态/状态转移方程什么的也就出来了。

我知道我这么说，可能楼主会觉得不靠谱，但是我也希望楼主能稍微考虑一下我说的。我觉得楼主可能需要和你一起刷题的人。楼主知道，人的聪明程度是不确定的，和心情和环境有很大很大的关系。我算是很佛系的人，但是要是和他人一起想问题的时候，我的确会比平时要聪明一些。可能是小小的虚荣心，也可能是头脑真的风暴了，反正就是聪明一些。而且有科学研究表明，大家一起锻炼的时候，也会比自己练更猛一些。我儿子就这样，在家里做chinup，做不了几个，但是在儿童体操班就能做很多个。

而且楼主心态已经不太好了，心情不好的时候，智商也得低几个点。

我现在就和我先生每周约一个时间pair coding一次（我们现在是异地）。我先生有那么一点好为人师，当他需要给我讲题的时候，感觉他也变聪明好几个点儿。

我知道人心情低落的时候就想自己呆着，但是那就真的没救了。但是从楼主来这里倾诉这一点看来，我觉得楼主是那种可以从人际交往中汲取力量的人。

找个人一起练吧。水平差不多，就互相帮助；如果你水平高，通过讲题能变更强；如果partner水平高，那就请他/她给你讲一讲，真人讲比看没有温度的文字，要好多了（当然这种情况，也要楼主用某种方式给予“老师”一些回报）。

dp我之前刷了好久也和你差不多，后来去youtube找了个dp套路，就是那个快5个小时的视频，好多原来做不出的题就都能做出来了。刷题刷烦了可以学会system design，过个半个月可能就又有动力刷了

补充内容 (2021-09-08 00:06 +8:00):
YouTube搜： 残酷刷题群算法小讲座：动态规划的套路 by wisdompeak

报个课或者去youtube看看别人是怎么刷题的：推荐basketwangcoding

摸摸LZ
可以换一下心情做点别的事情然后再继续刷

你如果现在刷dp的题目觉得很累可以先跳dp，做一些比较常规的题目，dp的题目都很活的。还有就是楼主心态要稍微改变一下，不要任务心理那么强，把刷题慢慢当成生活的习惯。如果楼主觉得自己坚持能力不行的话可以加一些刷题群或者找人互相打卡什么的，每当我觉得我可以休息一天的时候我看别人刷那么多题心里就有股不服气的想法，就又充满想刷题的想法了。

lz本科也是cs吗？我是想来劝退的，人生该放弃就放弃，一件事情很难做至少说明暂时不适合你，去找一个喜欢/能做好的工作不行吗？
中高考模式让人养成了蛇么都要努力达到的习惯，但努力已经发展成一个阻碍的时候太痛苦了。
“如果一件事情困难重重，不要觉得世界在为难你，世界是在帮你”

小亩_0d8a9d5 发表于 2021-9-6 20:05
dp我之前刷了好久也和你差不多，后来去youtube找了个dp套路，就是那个快5个小时的视频，好多原来做不出的题 ...

哪一个？求推荐

我才刷了20多道题，ssfd……
感觉压力好大，找全职和找intern心态完全不一样

小亩_0d8a9d5 发表于 2021-9-7 11:05
dp我之前刷了好久也和你差不多，后来去youtube找了个dp套路，就是那个快5个小时的视频，好多原来做不出的题 ...

哪个视频能否共享一下。谢谢