1340. Jump Game V

这个题目还是蛮入门的……

思路:

这题如果采用DP的思想去做,很难。第一,如果设$dp[t][i]$为第i个数字为终点,最多移动t步的情况下最大经过的数字个数,那么DP转移方程就涉及到搜索上一层合理数字,复杂度大增(离线可计算,但是还是不快)。

后面给的第二种算法就是该版本。

第二,如果$dp[t][i]$为第i个数字为起点,最多走t步的最大经过的数字个数,虽然由于顺着题目的意思,相比上一种方法减少了搜索上一层的合理数字,但还是不够快。可以从DP版本1中看出来,许多状态转移的计算都是无谓的。时间复杂度为$O(N^2D)$,即使有一点点剪枝也没法AC。

第三,通过记忆化搜索的方法,可以大幅减少重复计算。

Read more