小旭讲解 LeetCode. 1140 Stone Game II 石子游戏II
小旭讲解 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/
0 0 votes
Article Rating
Subscribe
提醒
guest
3 评论
Newest
Oldest Most Voted
Inline Feedbacks
View all comments

Sie können einfach unsere webseite nutzen da TikTok Follower kaufen legal ist verstößen sie nicht gegen die richtlinien von tiktok.

pożyczki

Strona, który jest poświęcony płaszczyźnie produktów sugerowanych przez parku bankowe, nieustannie rozbudowuje swą bazę. Raz za razem pojawiają się aktualne posty, oraz opinii pomagające podejmować stosowne wybory. Interesant bankowy zwiedzający własny serwis dowie się, gdzie banku warto prawdziwie ustanowić konto bankowe osobiste, tudzież w której placówce kretytowej najkorzystniejszy będzie zobowiązanie. Co więcej wskazówki kierowane dzięki obeznanych zawodowców upraszczają nakierować od akuratny wytwór skarbowy. Spośród newsów warto dowiedzieć się, iż nie ma co zdaje się być się sugerować chwytami marketingowymi. Aby poczuć satysfakcję jak i również pożytku , które wynikają wraz z włączonej transakcji powinno się zanalizować danemu produktowi nieco z większym natężeniem. Niezwykle wartościowe dzięki stronie okazują się aktualizowane porównywarki pieniężne. Za pomocą rankingom, jest dozwolone oszacować, która to inwestycja czy też jaki to kredyt mieszkaniowy w tym momencie okazuje się być faktycznie zyskowny. Pożądane byłoby pilnować nowości, jakie to są zamieszczane w portalu. Wtenczas warto zostać regularnie iz globem finansów, chwilówek, inwestycji a także różnorodnego gatunku ubezpieczeń. https://finanero.pl/pozyczki – Chwilówka bez sprawdzania.

trackback

2cobbler