小旭讲解 LeetCode. 1140 Stone Game II 石子游戏II

B站视频源

YouTube视频源

视频先后以两种思路——记忆化递归、动态规划讲解了如何解决《Stone Game II》(石子游戏II)问题。

如果大家有兴趣一起侃侃数据结构与算法,那么可以通过下面的微信号或者微信公众号给我留言(要带上自己的微信ID哦):

微信公众号(推荐):ihuxublog(胡小旭博客)

微信:genialx

如果你喜欢我的视频,可以到B站或者Youtube关注我~

记忆化递归

声明一个能够帮助解决问题的一个递归(辅助)函数,在声明函数时最重要的就是明确函数的含义——也就是这个函数到底能帮组我们解决什么问题?接着,再明确一下函数的入参。最后,回到问题,看看能否利用这个递归函数递归地解决问题。

在编写递归函数的主体时,要注意一点:

  • 边界条件的判断——错误的边界条件,会导致“死循环”或者提前退出调用栈

最后,为了能够达到更好的运行效果,可以为每一个子问题的解保留下来,以免重复计算——备忘录法。

小旭讲解-LeetCode. 1140-Stone-Game-II-石子游戏II-3
小旭讲解-LeetCode. 1140-Stone-Game-II-石子游戏II-3

代码

class Solution {
private:
    vector<int> acum;
    unordered_map<int, unordered_map<int, int>> memo;
    int dfs(vector<int>& piles, int start, int m) {
        if (memo.find(start) != memo.end() && memo[start].find(m) != memo[start].end()) return memo[start][m];
        if (start > piles.size() - 1) return 0;
        int max_stones = 0;
        for (int x = 1; x <= 2 *m; ++x) {
            int nm = max(x, m);
            int next_max_stones = dfs(piles, start + x, nm);
            max_stones = max(max_stones, acum[piles.size()] - acum[start] - next_max_stones);
        }
        return memo[start][m] = max_stones;
    }
public:
    int stoneGameII(vector<int>& piles) {
        int l = piles.size();
        acum = vector<int>(l + 1, 0);
        for (int i = 0; i < l; ++i) acum[i + 1] = acum[i] + piles[i];
        return dfs(piles, 0, 1);
    }
}; 

复杂度分析

时间复杂度:O(n ^ {3}) n = piles.size()

空间复杂度:O(n ^ {2})

动态规划

我们往往会疑惑一道题目到底能否用动态规划的方式解决?这个问题在我来看,经过多次的训练之后,发现其实也蛮简单的。

首先,我们可以利用题目给到的信息——如一维的数组,参数M等,来判断这样的一个大问题,能否分解成层层递进的,嵌套的若干个子问题。如果,觉得可以的话,那么第一件事儿就是要明确这个可以被分解的“状态空间”到底是什么?

接着,明确了本题的状态空间之后——dp[i][m],再分析不同阶段的状态空间相互之间是如何转移的——状态转移方程。

在有了状态转移方程之后,我们就可以很容易地将自底向上的代码编写出来了。

小旭讲解-LeetCode. 1140-Stone-Game-II-石子游戏II-3
小旭讲解-LeetCode. 1140-Stone-Game-II-石子游戏II-3
小旭讲解-LeetCode.-1140-Stone-Game-II-石子游戏II-5
小旭讲解-LeetCode.-1140-Stone-Game-II-石子游戏II-5
小旭讲解-LeetCode.-1140-Stone-Game-II-石子游戏II-6
小旭讲解-LeetCode.-1140-Stone-Game-II-石子游戏II-6
小旭讲解-LeetCode.-1140-Stone-Game-II-石子游戏II-7
小旭讲解-LeetCode.-1140-Stone-Game-II-石子游戏II-7
小旭讲解-LeetCode.-1140-Stone-Game-II-石子游戏II-8
小旭讲解-LeetCode.-1140-Stone-Game-II-石子游戏II-8
小旭讲解-LeetCode.-1140-Stone-Game-II-石子游戏II-9
小旭讲解-LeetCode.-1140-Stone-Game-II-石子游戏II-9
小旭讲解-LeetCode.-1140-Stone-Game-II-石子游戏II-10
小旭讲解-LeetCode.-1140-Stone-Game-II-石子游戏II-10
小旭讲解-LeetCode.-1140-Stone-Game-II-石子游戏II-11
小旭讲解-LeetCode.-1140-Stone-Game-II-石子游戏II-11

代码

class Solution {
public:
    int stoneGameII(vector<int>& piles) {
        int l = piles.size();
        vector<int> acum = vector<int>(l + 1, 0);
        for (int i = 0; i < l; ++i) acum[i + 1] = acum[i] + piles[i];
        vector<vector<int>> dp(l + 5, vector<int>(l + 5, 0));
        for (int i = l - 1; i >= 0; --i) {
            for (int m = 1; m <= i || m == 1; ++m) {
                for (int j = 1; j <= 2*m; ++j) {
                    if (i + j - 1 > piles.size() - 1) {
                        break;
                    } else {
                        dp[i][m] = max(dp[i][m], acum[l] - acum[i] - dp[i + j][max(m, j)]);
                    }
                }
            }
        }
        return dp[0][1];
    }
};  

复杂度分析

时间复杂度:O(n ^ {3}) n = piles.size()

空间复杂度:O(n ^ {2})


本文为原创文章,欢迎分享,勿全文转载,如果内容你实在喜欢,可以加入收藏夹,说不定哪天故事又继续更新了呢。
本文地址:https://qoogle.top/xiaoxu-explain-leetcode-1140-stone-game-ii/
最后修改日期:2019年11月25日

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。