?

Halo，這里是Ppeua。平時主要更新C語言，C++，數(shù)據(jù)結(jié)構(gòu)算法......感興趣就關(guān)注我吧！你定不會失望。

??個人主頁：主頁鏈接

??算法專欄：專欄鏈接

?????我會一直往里填充內(nèi)容噠！

??LeetCode專欄：專欄鏈接?

????目前在刷初級算法的LeetBook 。若每日一題當中有力所能及的題目，也會當天做完發(fā)出

??代碼倉庫：Gitee鏈接

??點擊關(guān)注=收獲更多優(yōu)質(zhì)內(nèi)容??

目錄

題目:戳氣球

題解:

代碼實現(xiàn):

完結(jié)撒花

因為一些事,最近狀態(tài)不是很好,加上今天的每日一題有點難,看的煩躁(就是菜 ,就來更新一下今天與每日一題相關(guān)的區(qū)間Dp問題(戳氣球),這篇也是關(guān)于區(qū)間Dp的問題 uu可以看看?

話不多說,開始!?

題目:戳氣球

題解:

這道題雖然被標為了Hard但依據(jù)Dp的特點,知道其中緣由之后也沒有很難了.先來看看問題

有這樣幾個氣球.我們要求出戳出他之后他掉落的最大金幣數(shù)

例如,在戳掉1,則掉落的金幣數(shù)為周圍兩個金幣數(shù)相乘,再乘上被戳掉的氣球的金幣數(shù)

在思考dp問題的時候,我們需要將每一個子問題劃分為不受周圍影響的獨立的子問題,所以觀察我們剛剛的計算過程.我們發(fā)現(xiàn),掉落的金幣數(shù)與i j是有關(guān)系的

題目提到:如果?i - 1或?i + 1?超出了數(shù)組的邊界，那么就當它是一個數(shù)字為?1?的氣球。

為了避免越界問題,那我們可以設(shè)定兩個虛擬氣球,他們得分都為1,這樣可以將dp的子問題劃分為

dp[i][j]的含義為:在i-1到j(luò)-1當中,戳破氣球獲得的最高分.

根據(jù)區(qū)間dp倒著推問題的特點:我們可以想想在i j當中,最后一個被戳爆的氣球是哪一個.

其實每一個氣球都能成為最后被戳破的那個,所以我們要做的就是在一定區(qū)間內(nèi)去尋找,戳破這個氣球,能獲得最大收益的k值

若想要最后一個戳破k,則需要先將i-k的氣球戳破,再將k-j的氣球戳破,之后再將結(jié)果加上戳破k區(qū)間的值即可(注意k是最后一個戳爆的!!他的周圍是沒有球的,所以這就是為什么是獨立的子問題的原因)

dp[i][j]=dp[i][k]+dp[k][j]+val[i]*val[j]*val[k]

觀察發(fā)現(xiàn),這是從小范圍去推大范圍,所以在計算大范圍的時候,小范圍一定是被準備好了.

所以從只有三個氣球的區(qū)間開始計算,慢慢拓展到大的區(qū)間.存儲每個區(qū)間可以獲得的最大金幣,留給之后計算

先看看Base Case是什么,當i j重合的時候,沒有東西可以戳,此時得分為0

當我們計算任何一個Dp[i][j]的時候,我們希望dp[i][k] 與dp[k][j]都已經(jīng)被計算出來了

所以我們一般采用,自底向上的遍歷方法.

相關(guān)模板:

for(int i=n;i>=0;i--)
    {
        for(int j=i+1;j<n;j++)
        {
            for(int k=i+1;k<j;k++)
            {
                ..........
            }
        }
    }

也就是i從n開始到0結(jié)束,j從i+1開始小于n(這里的n是指不能取到額外給的那兩個氣球),而k介于這二者之間?,為了避免越界問題,我們一般采用n+2的方法

代碼實現(xiàn):

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
class Solution {
public:
    int maxCoins(vector<int>& nums) {
        vector<int>val(nums.size()+2);
        val[0]=val[val.size()-1]=1;
        for(int i=1;i<=nums.size();i++)
        {
            val[i]=nums[i-1];
        }
        vector<vector<int>>dp(val.size(),vector<int>(val.size()));
        for(int i=val.size();i>=0;i--)
        {
            for(int j=i+1;j<val.size();j++)
            {
                for(int k=i+1;k<j;k++)
                {
                    dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]+val[i]*val[j]*val[k]);
                }
            }
        }
        return dp[0][val.size()-1];
    }
};

完結(jié)撒花：

??本篇博客的內(nèi)容【LeetCode 312. 戳氣球 --區(qū)間DP問題】已經(jīng)結(jié)束。

??若對你有些許幫助，可以點贊、關(guān)注、評論支持下博主，你的支持將是我前進路上最大的動力。

??若以上內(nèi)容有任何問題，歡迎在評論區(qū)指出。若對以上內(nèi)容有任何不解，都可私信評論詢問。

??諸君，山頂見！文章來源地址http://www.zghlxwxcb.cn/news/detail-415534.html

到了這里，關(guān)于【動態(tài)規(guī)劃】LeetCode 312. 戳氣球 --區(qū)間DP問題的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！