??博客介紹`： 27dCnc

??系列專欄： <<數(shù)據(jù)結(jié)構(gòu)與算法>> << 算法入門>> << C++項目>>

?? 當(dāng)前專欄: << 算法入門>>

專題 : 數(shù)據(jù)結(jié)構(gòu)幫助小白快速入門算法
????????????????????????
☆*: .?. o(≧▽≦)o .?.:*☆

??感謝大家點贊??收藏?評論??

學(xué)習(xí)目標(biāo)：

今日學(xué)習(xí)打卡

• 代碼隨想錄 - 動態(tài)規(guī)劃

學(xué)習(xí)時間：

• 周一至周五晚上 7 點—晚上9點
• 周六上午 9 點-上午 11 點
• 周日下午 3 點-下午 6 點

學(xué)習(xí)內(nèi)容：

1. 不同路徑
2. 不同路徑 II
3. 整數(shù)拆分

內(nèi)容詳細(xì)：

62.不同路徑

考點: 動態(tài)規(guī)劃 數(shù)學(xué) 深度優(yōu)先搜索(dfs)

解題思路
高中時候的組合規(guī)律,當(dāng)然我們不能直接這樣寫我們要進(jìn)行動態(tài)規(guī)劃分析

首先看到題目是想到dfs

class Solution {
private:
    int dfs(int i, int j, int m, int n) {
        if (i > m || j > n) return 0; // 越界了
        if (i == m && j == n) return 1; // 找到一種方法，相當(dāng)于找到了葉子節(jié)點
        return dfs(i + 1, j, m, n) + dfs(i, j + 1, m, n);
    }
public:
    int uniquePaths(int m, int n) {
        return dfs(1, 1, m, n);
    }
};

但是超時

開始動態(tài)規(guī)劃

1. 確定dp數(shù)組以及下標(biāo)的含義

dp[i][j] ：表示從（0 ，0）出發(fā)，到(i, j) 有dp[i][j]條不同的路徑。

2. 確定遞推公式(到這一步的方式)

想要求dp[i][j]，只能有兩個方向來推導(dǎo)出來，即dp[i - 1][j] 和 dp[i][j - 1]。

此時在回顧一下 dp[i - 1][j] 表示啥，是從(0, 0)的位置到(i - 1, j)有幾條路徑，dp[i][j - 1]同理。

那么很自然，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因為dp[i][j]只有這兩個方向過來。

3. dp數(shù)組的初始化
   這個就是高中的知識點

for (int i = 0; i < m; i++) dp[i][0] = 1;
for (int j = 0; j < n; j++) dp[0][j] = 1;

4. 確定遍歷順序
   這里要看一下遞推公式dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，dp[i][j]都是從其上方和左方推導(dǎo)而來，那么從左到右一層一層遍歷就可以了。

這樣就可以保證推導(dǎo)dp[i][j]的時候，dp[i - 1][j] 和 dp[i][j - 1]一定是有數(shù)值的。

5. 舉例推導(dǎo)dp數(shù)組
   
   最終代碼

class Solution {
public:
    int uniquePaths(int m, int n) {
        int dp[m][n];
        dp[0][0] = 0;
        for (int i = 0; i < m; i++) dp[i][0] = 1;
        for (int j = 0; j < n; j++) dp[0][j] = 1;
        for (int i = 1;i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = dp[i-1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};

63. 不同路徑 II

題目考點: 動態(tài)規(guī)劃

解題思路
和上一題一樣,只是多了障礙物,可以直接跳過,
如果遇到障礙物 continue

if (obstacleGrid[i][j] == 1) {continue;}

i 代碼

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int l,r;
        int m =obstacleGrid.size();
        int n = obstacleGrid[0].size();
        int dp[m][n];
        if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1){
            return 0;
        }
        memset(dp,0,sizeof(dp));
        for (int i = 0; i < m && !obstacleGrid[i][0]; i++) dp[i][0] = 1;
        for (int j = 0; j < n && !obstacleGrid[0][j]; j++) dp[0][j] = 1;
        for (int i = 1;i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {continue;}
                dp[i][j] = dp[i-1][j] + dp[i][j - 1];
            }
        }
        return dp[m - 1][n - 1];
    }
};

ii 代碼

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        if (obstacleGrid[0][0] == 1)
            return 0;
        vector<int> dp(obstacleGrid[0].size());
        for (int j = 0; j < dp.size(); ++j)
            if (obstacleGrid[0][j] == 1)
                dp[j] = 0;
            else if (j == 0)
                dp[j] = 1;
            else
                dp[j] = dp[j-1];

        for (int i = 1; i < obstacleGrid.size(); ++i)
            for (int j = 0; j < dp.size(); ++j){
                if (obstacleGrid[i][j] == 1)
                    dp[j] = 0;
                else if (j != 0)
                    dp[j] = dp[j] + dp[j-1];
            }
        return dp.back();
    }
};

343. 整數(shù)拆分

題目考點: 動態(tài)規(guī)劃

解題思路

可以拆分成多個數(shù)據(jù)對動態(tài)規(guī)劃實行貪心,max就是貪心的具象化,(個人理解)

其他步驟省,這里詳細(xì)講解

• 確定遞推公式

可以想 dp[i]最大乘積是怎么得到的呢？

其實可以從1遍歷j，然后有兩種渠道得到dp[i].

一個是j * (i - j) 直接相乘。

一個是j * dp[i - j]，相當(dāng)于是拆分(i - j)，對這個拆分不理解的話，可以回想dp數(shù)組的定義。

那有同學(xué)問了，j怎么就不拆分呢？

j是從1開始遍歷，拆分j的情況，在遍歷j的過程中其實都計算過了。那么從1遍歷j，比較(i - j) * j和dp[i - j] * j 取最大的。
遞推公式：

dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));

也可以這么理解，j * (i - j) 是單純的把整數(shù)拆分為兩個數(shù)相乘，而j * dp[i - j]是拆分成兩個以及兩個以上的個數(shù)相乘。

• 如果定義dp[i - j] * dp[j] 也是默認(rèn)將一個數(shù)強(qiáng)制拆成4份以及4份以上了。

• 所以遞推公式：dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});

• 那么在取最大值的時候，為什么還要比較dp[i]呢？

因為在遞推公式推導(dǎo)的過程中，每次計算dp[i]，取最大的而已。

class Solution {
public:
    int integerBreak(int n) {
        if(n < 4) return n/2 * (n - n/2);
        int dp[n+4];
        memset(dp,0,sizeof dp);
        dp[2] = 1;
        for (int i = 3; i <= n ; i++) {
            for (int j = 1; j <= i / 2; j++) {
                dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});
            }
        }
        return dp[n];
    }
};

學(xué)習(xí)產(chǎn)出：

• 技術(shù)筆記 2 遍
• CSDN 技術(shù)博客 3 篇
• 習(xí)的 vlog 視頻 1 個

重磅消息:

GTP - 4 最新版接入服務(wù)他來了 點擊鏈接即可查看詳細(xì)

GTP - 4 搭建教程

??如果此文對你有幫助的話，歡迎??關(guān)注、??點贊、?收藏、??評論，支持一下博主~文章來源地址http://www.zghlxwxcb.cn/news/detail-838681.html

到了這里，關(guān)于我在代碼隨想錄|寫代碼Day33 | 動態(tài)規(guī)劃| 路徑問題| 62.不同路徑,63. 不同路徑 II,343. 整數(shù)拆分的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！