国产无码综合区,色欲AV无码国产永久播放,无码天堂亚洲国产AV,国产日韩欧美女同一区二区

<table id="55c5t"><listing id="55c5t"><rt id="55c5t"></rt></listing></table>

<samp id="55c5t"></samp>

^{<rp id="55c5t"></rp>}

<rp id="55c5t"></rp>
<ul id="55c5t"><tr id="55c5t"><noscript id="55c5t"></noscript></tr></ul>

2023-05-02 動態(tài)規(guī)劃簡介

2年前作者：空無一悟分類：Toy博客閱讀(20)違法舉報

這篇具有很好參考價值的文章主要介紹了2023-05-02 動態(tài)規(guī)劃簡介。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

動態(tài)規(guī)劃簡介

1 動態(tài)規(guī)劃的基本概念

階段、狀態(tài)、決策、策略、狀態(tài)轉(zhuǎn)移方程

1) 階段和階段變量

將問題的全過程恰當(dāng)?shù)胤殖扇舾蓚€相互聯(lián)系的階段閆氏DP分析法：對應(yīng)f[i][j]的ij遍歷時形成的所有f[i][j]
階段的劃分一般根據(jù)時間和空間的自然特征去劃分
階段的劃分便于把問題轉(zhuǎn)化成多階段決策問題

2) 狀態(tài)和狀態(tài)變量

通常一個階段包含若干狀態(tài)

閆氏DP分析法：每個階段分多種情況
狀態(tài)可由變量來描述

3) 決策、決策變量和決策允許集合

決策：在對問題的處理中作出的每種選擇性的行動閆氏DP分析法：對應(yīng)狀態(tài)計算

即從該階段的每一個狀態(tài)出發(fā)，通過一次選擇性的行動轉(zhuǎn)移至下一階段的相應(yīng)狀態(tài)對應(yīng)閆氏DP分析法：即狀態(tài)轉(zhuǎn)移
決策變量：一個實際問題可能需要有多次決策和多個決策點，在每個階段的每個狀態(tài)中都需要有一次決策，決策可以用變量來描述，稱這種變量為決策變量
決策允許集合：在實際問題中，決策變量的取值范圍

4) 策略和最優(yōu)策略

對應(yīng)閆式DP分析法的"屬性：max、min、cnt"

策略：所有階段依次排列構(gòu)成問題的全過程，全過程中各階段決策變量所組成的有序總體稱為策略

策略一般對應(yīng)實際問題的一種解。簡單說就是每個階段選一個狀態(tài)按照某種決策規(guī)律連起來組成的一條鏈路
最優(yōu)策略：在實際問題中，從允許決策集合中找出最優(yōu)效果的策略稱為最優(yōu)策略

最優(yōu)策略一般對應(yīng)實際問題的最優(yōu)解，這個也是大部分DP題目的目標(biāo)

以數(shù)塔問題為例，舉例如下：
2023-05-02 動態(tài)規(guī)劃簡介

5) 狀態(tài)轉(zhuǎn)移方程

上個階段狀態(tài)到下個階段狀態(tài)的決策規(guī)律

前一階段的終點的就是后一階段的起點
對前一階段的狀態(tài)做出某種決策，產(chǎn)生后一種階段的狀態(tài)
這種關(guān)系描述了從i階段到i+1階段的演變規(guī)律，稱為狀態(tài)轉(zhuǎn)移方程

即從dp[i]到dp[i+1]的計算公式

2023-05-02 動態(tài)規(guī)劃簡介

6) 舉例

2023-05-02 動態(tài)規(guī)劃簡介

1.階段：長條
2.狀態(tài)：小圓圈
3.決策：長條內(nèi)的小圓圈轉(zhuǎn)移到下一個長條內(nèi)的小圓圈

決策集合就是所有的轉(zhuǎn)移可能，即圖中的箭頭
4.策略：從第一個長條(階段)到最后一個長條，每個長條選一個狀態(tài)(小圓圈)用箭頭(決策)連接起來的一條鏈路

最優(yōu)策略就是所有策略中滿足最值的一條鏈路(最大值max、最小值min、計數(shù)cnt、是否存在exist的等)
5.狀態(tài)轉(zhuǎn)移方程：從上一個狀態(tài)到下一個狀態(tài)的轉(zhuǎn)移方程式，按照這個方程式得到的策略就是最優(yōu)策略

結(jié)合上面總結(jié)的5個概念，來嘗試解決兩個問題

舉例1：從n個數(shù)的數(shù)組 $a [n]$ 中取出k個數(shù)，使得他們的和最大

$f [i] [j]$ 表示從第1個數(shù)到第i個數(shù)之間，已經(jīng)選取了j個數(shù)，其和最大的值

階段：階段[i](即 $f [i]$ )指前i個數(shù)組成的序列
狀態(tài)：j，即前i個數(shù)中選取了j個數(shù)， $0 \leq j \leq i$
決策：可選的決策集合如下,第i個數(shù)表示前i個數(shù)的最后一個數(shù)，閆氏分析法叫"最后一個不同點"
- A.取 $第 i 個數(shù) a [i]$ 到最終的j個數(shù)中：?? $f [i] [j] = f [i ? 1] [j ? 1] + f [i]$
- B.不取 $第 i 個數(shù) a [i]$ 到最終的j個數(shù)中： $f [i] [j] = f [i ? 1] [j]$
策略：使得f[i][j]盡量大，即取決策A和B的較大者

對應(yīng)閆氏分析法的max
狀態(tài)轉(zhuǎn)移方程：滿足最優(yōu)策略的方程，即 $max\lbrace a[i] + f[i - 1][j - 1], f[i - 1][j]\rbrace$

舉例2：從n個數(shù)的數(shù)組a[n]中找出最長上升子序列的元素個數(shù)

f[i]表示[a[0]~a[i]]組成的序列中且最后一個數(shù)是a[i]的最長上升子序列的長度

階段：階段[i](即 $f [i]$ )指前i+1個數(shù)組成的序列，注意下標(biāo)從0開始
狀態(tài)：i前面某個位置j處的數(shù)a[j]，作為最長上升子序列的前一個值(因為a[i]必須是最長上升子序列的最后一個值)

階段內(nèi)的多個狀態(tài)就是指j在范圍 $0 \leq j < i$ 內(nèi)取變所有值的對應(yīng)a[j]
決策：根據(jù)a[j]是否小于a[i]，決定a[j]是否在以a[i]結(jié)尾的上升子序列中
- $a [j] < a [i]$ : 滿足最長上升子序列要求，即a[j]在以a[i]結(jié)尾的上升子序列中，所以更新以a[i]結(jié)尾的最長子序列長度 $max\lbrace f[i], f[j] + 1 \mid 0≤j<i\rbrace$
- $a [j] >= a [i]$ ：不滿足最長上升子序列的要求，即a[j]不在以a[i]結(jié)尾的上升子序列中，不更新以a[i]結(jié)尾的最長子序列長度，直接跳過即可
策略：在 $0 \leq j < i$ 范圍內(nèi)，不斷根據(jù)a[j]的值刷新f[i]，獲取f[i]的最大值
狀態(tài)轉(zhuǎn)移方程： $max\lbrace f[i], f[j] + 1 \mid 0≤j<i\rbrace$

題目見：300. 最長上升子序列

class Solution {
public:
    int lengthOfLIS(vector<int> &a) {
        if (a.empty()) return 0;

        int N = a.size();
        // f[i]表示[a[0]~a[i]]組成的序列中且最后一個數(shù)是a[i]的最長上升子序列的長度
        vector<int> f(N, 1); // 初始化一個都為1的二維數(shù)組,即每個元素至少自己都是一個上升子序列
        int res = 1; // 初始化最小值為1
        for (int i = 1; i < N; i++) {
            for (int j = 0; j < i; j++) {
                if (a[j] < a[i]) {
                    f[i] = max(f[i], f[j] + 1);
                }
            }
            res = max(res, f[i]);
        }
        return res;
    }
};

2 動態(tài)規(guī)劃的性質(zhì)

動態(tài)規(guī)劃適用的問題需要滿足的條件？

什么樣的"多階段決策問題"才可以用動態(tài)規(guī)劃的方法來求解呢？前提是能劃分階段，然后必須滿足下面兩個條件

1） 最優(yōu)化原理

作為整個過程的最優(yōu)策略，具有：無論過去的狀態(tài)和策略如何，對前面的決策所形成的狀態(tài)而言，余下的所有決策必須構(gòu)成最優(yōu)策略的性質(zhì)，即
- 子問題的局部最優(yōu)會促成整個問題的全局最優(yōu)
- 問題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)
- 一個問題的最優(yōu)解只取決于其子問題的最優(yōu)解
2） 無后效性原則
- 某階段的狀態(tài)一旦確定，則此后過程的演變不再受此前各狀態(tài)及決策的影響，即“未來與過去無關(guān)"
- 當(dāng)前的狀態(tài)是此前歷史的一個完整的總結(jié)，此前的歷史只能通過當(dāng)前的狀態(tài)去影響過程在未來的演變，即"未來只會被現(xiàn)在影響”

不能用動態(tài)規(guī)劃來做的題

誤用動態(tài)規(guī)劃會得到錯誤的結(jié)果

對于不能劃分階段的題，不能用動態(tài)規(guī)劃來解
不符合最優(yōu)化原理，不能用動態(tài)規(guī)劃來解
不具備無后效性原則的，不能用動態(tài)規(guī)劃來解

動態(tài)規(guī)劃的設(shè)計方法

正推：從初始狀態(tài)開始，通過對中間階段的決策的選擇，達到結(jié)束狀態(tài)，我們也稱遞推
倒推：從結(jié)束狀態(tài)開始，通過對中間階段的決策的選擇，達到開始狀態(tài)。我們可以把這種方法看成記憶化搜索

動態(tài)規(guī)劃設(shè)計方法的一般模式

1和2相當(dāng)于閆氏DP分析法的確定集合(即明確f[i][j]的含義，即狀態(tài)表示)；3相當(dāng)于閆氏DP分析法里的狀態(tài)計算，即確定每個階段的所有轉(zhuǎn)移可能情況，然后獲取目標(biāo)的屬性值(max、min、cnt等)

1）劃分階段
2）確定狀態(tài)和狀態(tài)變量

一般是確定f[i][j]中j的定義(即狀態(tài))和范圍(如 $a \leq j < b$ 即狀態(tài)變量)
3）確定決策并寫出狀態(tài)轉(zhuǎn)移方程

按照f[i][j]中i的定義確定決策集合，根據(jù)目標(biāo)屬性(max、min、cnt、存在等)得出狀態(tài)轉(zhuǎn)移方程
4）尋找邊界條件

根據(jù)題目給出的變量范圍，小心帶入狀態(tài)變量和決策集合的值到狀態(tài)轉(zhuǎn)移方程中，得到最終的目標(biāo)屬性值
5）設(shè)計并實現(xiàn)程序

寫好、實現(xiàn)好1~4的步驟對應(yīng)的代碼，并通過一些動態(tài)規(guī)劃的優(yōu)化技巧進行性能提升

3 動態(tài)規(guī)劃與記憶化搜索

記憶化搜索的概念

實現(xiàn)一個函數(shù)，用"搜索"的方式實現(xiàn)DP的更新，通常用于解決狀態(tài)轉(zhuǎn)移順序不方便人為確定的DP

例題：AcWing898:數(shù)字三角形

題目大意：

輸入一個n層的三角形，第i層有i個數(shù)，求從第1層到第n層的所有路線中，權(quán)值之和最大的路線。
規(guī)定：第i層的某個數(shù)只能連線走到第i+1層中與它位置相鄰的兩個數(shù)中的一個。

普通遞歸實現(xiàn)，會超時，給的例子進入遞歸217次

/**
 * 數(shù)塔問題
 * https://www.acwing.com/problem/content/900/
 */

#include <iostream>
#include <vector>

using namespace std;

#define INF 0x3f3f3f3f

/**
 * 分解為最優(yōu)子結(jié)構(gòu)問題，先求局部最優(yōu)解
 * @param i 第i行(下標(biāo)從0開始)
 * @param j 第j列(下標(biāo)從0開始)
 * @return 從上往下到達元素nums[i][j]的最大路徑和
 */
int SubSolve(vector<vector<int>> &nums, int i, int j) {
    if (i < 0 || j < 0) return 0; // 必須保證退出
    // 決策
    if (j - 1 >= 0) {
        if (j <= i - 1) { // 左上和右上元素都有
            return nums[i][j] + max(SubSolve(nums, i - 1, j), SubSolve(nums, i - 1, j - 1)); // 決策集合包括左上和右上兩個元素
        } else { // 沒有右上元素
            return nums[i][j] + SubSolve(nums, i - 1, j - 1); // 決策集合只有左上元素
        }
    } else { // 沒有左上元素
        return nums[i][j] + SubSolve(nums, i - 1, j); // 決策集合只有右上元素
    }
}

/**
 * 統(tǒng)計最后一行的所有子問題最優(yōu)解，其中最大的就是最終結(jié)果
 * @param nums 存儲三角形的數(shù)組
 * @return 最大的路徑和
 */
int Solve(vector<vector<int>> &nums) {
    int res = -INF;
    int n = nums.size();
    for (int j = 0; j < n; j++) {
        res = max(res, SubSolve(nums, n - 1, j));
    }
    return res;
}

int main() {
    int N;
    cin >> N;
    vector<vector<int>> v(N, vector<int>(N, 1e9)); // 二維數(shù)組初始化為很大的數(shù)，防止干擾數(shù)據(jù)判斷
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) {
            cin >> v[i][j];
        }
    }
    cout << Solve(v) << endl;
    return 0;
}

記憶化搜索，雖然提高了效率，進入遞歸次數(shù)變成了87次，但是仍然超時

/**
 * 數(shù)塔問題
 * https://www.acwing.com/problem/content/900/
 */

#include <iostream>
#include <vector>

using namespace std;

#define INF 0x3f3f3f3f

/**
 * 分解為最優(yōu)子結(jié)構(gòu)問題，先求局部最優(yōu)解
 * @param i 第i行(下標(biāo)從0開始)
 * @param j 第j列(下標(biāo)從0開始)
 * @return 從上往下到達元素nums[i][j]的最大路徑和
 */
int SubSolve(vector<vector<int>> &nums, int i, int j, vector<vector<int>> &dp) {
    if (i < 0 || j < 0) return 0; // 必須保證退出
    // 決策
    if (j - 1 >= 0) {
        if (j <= i - 1) { // 左上和右上元素都有
            dp[i][j] = nums[i][j] + max(SubSolve(nums, i - 1, j, dp), SubSolve(nums, i - 1, j - 1, dp)); // 決策集合包括左上和右上兩個元素
        } else { // 沒有右上元素
            dp[i][j] = nums[i][j] + SubSolve(nums, i - 1, j - 1, dp); // 決策集合只有左上元素
        }
    } else { // 沒有左上元素
        dp[i][j] = nums[i][j] + SubSolve(nums, i - 1, j, dp); // 決策集合只有右上元素
    }
    return dp[i][j];
}

/**
 * 統(tǒng)計最后一行的所有子問題最優(yōu)解，其中最大的就是最終結(jié)果
 * @param nums 存儲三角形的數(shù)組
 * @return 最大的路徑和
 */
int Solve(vector<vector<int>> &nums) {
    int res = -INF;
    int n = nums.size();
    vector<vector<int>> dp(n, vector<int>(n, -INF)); // 記憶數(shù)組，初始化為最小值
    for (int j = 0; j < n; j++) {
        res = max(res, SubSolve(nums, n - 1, j, dp));
    }
    return res;
}

int main() {
    int N;
    cin >> N;
    vector<vector<int>> v(N, vector<int>(N, 1e9)); // 二維數(shù)組初始化為很大的數(shù)，防止干擾數(shù)據(jù)判斷
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) {
            cin >> v[i][j];
        }
    }
    cout << Solve(v) << endl;
    return 0;
}

動態(tài)規(guī)劃實現(xiàn)，唯一不超時的實現(xiàn)

/**
 * 數(shù)塔問題
 * https://www.acwing.com/problem/content/900/
 */

#include <iostream>
#include <vector>

#define INF 0x3f3f3f3f

using namespace std;

/**
 * 統(tǒng)計最后一行的所有子問題最優(yōu)解，其中最大的就是最終結(jié)果
 * @param nums 存儲三角形的數(shù)組
 * @return 最大的路徑和
 */
int Solve(vector<vector<int>> &nums) {
    int res = -INF;
    int n = nums.size();
    vector<vector<int>> dp(n, vector<int>(n, -INF)); // 求最大距離，因此初始化為最小值
    dp[0][0] = nums[0][0];
    for (int i = 1; i < n; i++) { // 階段
        for (int j = 0; j <= i; j++) { // 狀態(tài)(變量)
            // 決策
            if (j - 1 >= 0) {
                if (j <= i - 1) { // 左上和右上元素都有
                    dp[i][j] = nums[i][j] + max(dp[i - 1][j], dp[i - 1][j - 1]); // 決策集合包括左上和右上兩個元素
                } else { // 沒有右上元素
                    dp[i][j] = nums[i][j] + dp[i - 1][j - 1]; // 決策集合只有左上元素
                }
            } else { // 沒有左上元素
                dp[i][j] = nums[i][j] + dp[i - 1][j]; // 決策集合只有右上元素
            }
        }
    }
    for (int j = 0; j < n; j++) {
        res = max(res, dp[n - 1][j]);
    }
    return res;
}

int main() {
    int N;
    cin >> N;
    vector<vector<int>> v(N, vector<int>(N, -INF)); // 二維數(shù)組初始化為很大的數(shù)，防止干擾數(shù)據(jù)判斷
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) {
            cin >> v[i][j];
        }
    }
    cout << Solve(v) << endl;
    return 0;
}

本問題的動態(tài)規(guī)劃淺析

$d p [i] [j]$ 表示第i行第j列對應(yīng)的最長路徑和

階段： $d p [i]$ 即第i行，每行為一個階段
狀態(tài)： $d p [i] [j]$ 第j列，狀態(tài)變量為j，其取值范圍為 $0 \leq j \leq i$
決策：決策為當(dāng)前狀態(tài)dp[i][j]從哪個狀態(tài)轉(zhuǎn)移過來(不同的轉(zhuǎn)移點即為決策集合)，分析題目可知可選的決策集合如下
- A.從左上角轉(zhuǎn)移過來： $d p [i] [j] = n u m s [i] [j] + d p [i ? 1] [j ? 1]$
- B.從右上角轉(zhuǎn)移過來： $d p [i] [j] = n u m s [i] [j] + d p [i ? 1] [j]$
策略：最優(yōu)策略是使得dp[i][j]盡量大，即取決策A和B的較大者

對應(yīng)閆氏分析法的max
狀態(tài)轉(zhuǎn)移方程：滿足最優(yōu)策略的方程，即 $max\lbrace nums[i][j] + dp[i - 1][j - 1], nums[i][j] + dp[i - 1][j]\rbrace$ ，提取出 $n u m s [i] [j]$ 得到 $max\lbrace dp[i - 1][j - 1], dp[i - 1][j]\rbrace$
邊界條件：注意左上角點或右上角點不存在的情況，區(qū)分三種情況計算 $d p [i] [j]$

例題：AcWing901：滑雪

該題不能用動態(tài)規(guī)劃做，因為沒法劃分狀態(tài)

純遞歸，會超時

累計進入遞歸912次

/**
 * 滑雪：不好劃分階段，只能用記憶化搜索做，不能用動態(tài)規(guī)劃做
 * https://www.acwing.com/problem/content/903/
 */

#include <iostream>
#include <vector>

using namespace std;

int R, C;
int dirs[4][2] = {
        {0,  1},
        {1,  0},
        {-1, 0},
        {0,  -1}
};
vector<vector<int>> grid;
vector<vector<bool>> visited;

bool inGrid(int r, int c) {
    return r >= 0 && r < R && c >= 0 && c < C;
}

/**
 * 從位置(r, c)開始滑雪，看能滑的長度距離
 */
int solve(int r, int c) {
    visited[r][c] = true;

    int dis = 0; // (r, c的鄰接點中可以滑雪的最大長度
    for (auto &dir : dirs) {
        int rNext = r + dir[0];
        int cNext = c + dir[1];
        if (inGrid(rNext, cNext) && !visited[rNext][cNext] && grid[rNext][cNext] < grid[r][c]) {
            int childMax = solve(rNext, cNext);
            dis = max(dis, childMax);
            visited[rNext][cNext] = false;
        }
    }
    return dis + 1; // + 1是因為當(dāng)前點(r, c)也算一個距離
}

int main() {
    /** 1.初始化數(shù)據(jù) */
    cin >> R >> C;
    grid.resize(R, vector<int>(C, 0));
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> grid[i][j];
        }
    }

    /** 2.從每個點開始嘗試DFS */
    int res = 0; // 求最大值，所以初始化為最小值
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            visited.clear();
            visited.resize(R, vector<bool>(C, false)); // 訪問數(shù)據(jù)重新初始化
            res = max(res, solve(r, c));
        }
    }
    cout << res << endl;
    return 0;
}

記憶數(shù)組，仍然超時

累計進入遞歸65次

/**
 * 滑雪：不好劃分階段，只能用記憶化搜索做，不能用動態(tài)規(guī)劃做
 * https://www.acwing.com/problem/content/903/
 */

#include <iostream>
#include <vector>

using namespace std;

int R, C;
int dirs[4][2] = {
        {0,  1},
        {1,  0},
        {-1, 0},
        {0,  -1}
};
vector<vector<int>> grid;
vector<vector<bool>> visited;
vector<vector<int>> dp;

bool inGrid(int r, int c) {
    return r >= 0 && r < R && c >= 0 && c < C;
}

/**
 * 從位置(r, c)開始滑雪，看能滑的長度距離
 */
int solve(int r, int c) {
    visited[r][c] = true;
    if (dp[r][c] > 0) {
        return dp[r][c];
    }

    int dis = 0; // (r, c的鄰接點中可以滑雪的最大長度
    for (auto &dir : dirs) {
        int rNext = r + dir[0];
        int cNext = c + dir[1];
        if (inGrid(rNext, cNext) && !visited[rNext][cNext] && grid[rNext][cNext] < grid[r][c]) {
            int childMax = solve(rNext, cNext);
            dis = max(dis, childMax);
            visited[rNext][cNext] = false;
        }
    }
    dp[r][c] = dis + 1; // + 1是因為當(dāng)前點(r, c)也算一個距離
    return dp[r][c];
}

int main() {
    /** 1.初始化數(shù)據(jù) */
    cin >> R >> C;
    grid.resize(R, vector<int>(C, 0));
    dp.resize(R, vector<int>(C, 0)); // 記憶每個子節(jié)點的狀態(tài)
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> grid[i][j];
        }
    }

    /** 2.從每個點開始嘗試DFS */
    int res = 0; // 求最大值，所以初始化為最小值
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            visited.clear(); // 如果之前賦值過，重新resize前務(wù)必記得clear一下，否則之前的數(shù)據(jù)仍然會存在
            visited.resize(R, vector<bool>(C, false)); // 訪問數(shù)據(jù)重新初始化
            res = max(res, solve(r, c));
        }
    }
    cout << res << endl;
    return 0;
}

記憶數(shù)組，去掉訪問數(shù)組，通過

看來訪問數(shù)組還挺耗性能呀

/**
 * 滑雪：不好劃分階段，只能用記憶化搜索做，不能用動態(tài)規(guī)劃做
 * https://www.acwing.com/problem/content/903/
 */

#include <iostream>
#include <vector>

using namespace std;

int R, C;
int dirs[4][2] = {
        {0,  1},
        {1,  0},
        {-1, 0},
        {0,  -1}
};
vector<vector<int>> grid;
vector<vector<int>> dp;

bool inGrid(int r, int c) {
    return r >= 0 && r < R && c >= 0 && c < C;
}

/**
 * 從位置(r, c)開始滑雪，看能滑的長度距離
 */
int solve(int r, int c) {
    if (dp[r][c] > 0) { // 遍歷過直接返回了，起到了訪問數(shù)組的作用
        return dp[r][c];
    }

    int dis = 0; // (r, c的鄰接點中可以滑雪的最大長度
    for (auto &dir : dirs) {
        int rNext = r + dir[0];
        int cNext = c + dir[1];
        if (inGrid(rNext, cNext) && grid[rNext][cNext] < grid[r][c]) {
            int childMax = solve(rNext, cNext);
            dis = max(dis, childMax);
        }
    }
    dp[r][c] = dis + 1; // + 1是因為當(dāng)前點(r, c)也算一個距離
    return dp[r][c];
}

int main() {
    /** 1.初始化數(shù)據(jù) */
    cin >> R >> C;
    grid.resize(R, vector<int>(C, 0));
    dp.resize(R, vector<int>(C, 0)); // 記憶每個子節(jié)點的狀態(tài)
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> grid[i][j];
        }
    }

    /** 2.從每個點開始嘗試DFS */
    int res = 0; // 求最大值，所以初始化為最小值
    for (int r = 0; r < R; r++) {
        for (int c = 0; c < C; c++) {
            res = max(res, solve(r, c));
        }
    }
    cout << res << endl;
    return 0;
}

本問題不能用動態(tài)規(guī)劃來做的原因淺析

因為狀態(tài)轉(zhuǎn)移順序不方便人為確定，所以此題不能用動態(tài)規(guī)劃來做。下面按照動態(tài)規(guī)劃的步驟進行分析

dp[i][j]表示第i行第j列的元素作為起點開始滑雪，能滑的最遠(yuǎn)距離

階段： $d p [i]$ 即第i行，每行為一個階段
狀態(tài)： $d p [i] [j]$ 第j列，狀態(tài)變量為j，其取值范圍為 $0 \leq j ＜ C$
決策：決策為當(dāng)前狀態(tài)dp[i][j]從哪個狀態(tài)轉(zhuǎn)移過來(不同的轉(zhuǎn)移點即為決策集合)，分析題目可知可選的決策集合如下(假設(shè)滿足題目要求的其他限制條件地前提下，如必須高度遞減往下滑和不能出邊界等)
- A.從左邊轉(zhuǎn)移過來： $d p [i] [j] = g r i d [i] [j ? 1] + 1$
- B.從右邊轉(zhuǎn)移過來： $d p [i] [j] = g r i d [i] [j + 1] + 1$
- C.從上面轉(zhuǎn)移過來： $d p [i] [j] = g r i d [i ? 1] [j] + 1$
- D.從下面轉(zhuǎn)移過來： $d p [i] [j] = g r i d [i + 1] [j] + 1$
從上面四種決策可知，要得到dp[i][j]，必須要先計算出i+1、i-1、j+1、j-1四種狀態(tài)對應(yīng)的值，但是dp中的for循環(huán)都是單向遞增或遞減的，不可能同時算出i前面和后面、j前面和后面的狀態(tài)值，因此這四種決策無法同時得到，因此也就沒有下面的最優(yōu)策略計算了，故動態(tài)規(guī)劃不能用了文章來源地址http://www.zghlxwxcb.cn/news/detail-435359.html

到了這里，關(guān)于2023-05-02 動態(tài)規(guī)劃簡介的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！

本文來自互聯(lián)網(wǎng)用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務(wù)，不擁有所有權(quán)，不承擔(dān)相關(guān)法律責(zé)任。如若轉(zhuǎn)載，請注明出處：如若內(nèi)容造成侵權(quán)/違法違規(guī)/事實不符，請點擊違法舉報進行投訴反饋，一經(jīng)查實，立即刪除！

分享到：

領(lǐng)支付寶紅包贊助服務(wù)器費用

動態(tài)規(guī)劃02-斐波那契類型二
給你一個整數(shù)數(shù)組 cost ，其中 cost[i] 是從樓梯第 i 個臺階向上爬需要支付的費用。一旦你支付此費用，即可選擇向上爬一個或者兩個臺階。你可以選擇從下標(biāo)為 0 或下標(biāo)為 1 的臺階開始爬樓梯。請你計算并返回達到樓梯頂部的最低花費。真題點擊此處：746.使用最小花費爬樓
2024年01月16日
瀏覽(15)
Day36算法記錄|動態(tài)規(guī)劃 dp02
步驟回顧： C語言版本寫的很清楚對應(yīng)得Java版本視頻解析方法一：動態(tài)規(guī)劃 1 確定dp數(shù)組（dp table）以及下標(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]。 3. dp數(shù)
2024年02月12日
瀏覽(24)
【算法】動態(tài)規(guī)劃 ① ( 動態(tài)規(guī)劃簡介 | 自底向上的動態(tài)規(guī)劃示例 | 自頂向下的動態(tài)規(guī)劃示例 )
動態(tài)規(guī)劃 , 英文名稱 Dynamic Programming , 簡稱 DP , 不是具體的某種算法 , 是一種算法思想 ; 具體的算法都有具體的步驟 , 如 : 二分法 , 其有固定的解決步驟 , 先取一個中心點 , 判斷解在左邊還是右邊 , 然后在一邊再取一個中心點 , 再進行判定 , 該算法有具體的步驟 ; 動態(tài)規(guī)劃
2024年01月16日
瀏覽(24)
Day43｜動態(tài)規(guī)劃part05： 1049. 最后一塊石頭的重量 II、494. 目標(biāo)和、474. 一和零
本題物品的重量為stones[i]，物品的價值也為stones[i]。對應(yīng)著01背包里的物品重量weight[i]和物品價值value[i]。確定dp數(shù)組以及下標(biāo)的含義 dp[j]表示容量（這里說容量更形象，其實就是重量）為j的背包，最多可以背最大重量為dp[j] 。確定遞推公式 01背包的遞推公式為：dp[j] = ma
2024年04月23日
瀏覽(26)
動態(tài)規(guī)劃機試2023.4.19
eg12.1 N階樓梯上樓問題 ex12.1 吃糖果和（eg12.1的程序一模一樣） eg12.2 最大序列和 eg12.3 最大子矩陣（北京大學(xué)復(fù)試上機題）復(fù)習(xí)了二維前綴和并且使用暴力做法解出該題 ex12.2 最大連續(xù)子序列（浙江大學(xué)復(fù)試上機題）使用前綴和 eg12.4 攔截導(dǎo)彈（北京大學(xué)復(fù)試上機題）最大不
2023年04月22日
瀏覽(18)
【LeetCode題目詳解】第九章動態(tài)規(guī)劃 part05 1049. 最后一塊石頭的重量 II 494. 目標(biāo)和 474.一和零（day43補）
有一堆石頭，用整數(shù)數(shù)組? stones 表示。其中? stones[i] 表示第 i 塊石頭的重量。每一回合，從中選出任意兩塊石頭，然后將它們一起粉碎。假設(shè)石頭的重量分別為? x 和? y ，且? x = y 。那么粉碎的可能結(jié)果如下：如果? x == y ，那么兩塊石頭都會被完全粉碎；如果? x != y
2024年02月09日
瀏覽(25)
代碼隨想錄Day36 動態(tài)規(guī)劃05 LeetCode T1049最后一塊石頭的重量II T494 目標(biāo)和 T474 一和零
理論基礎(chǔ)? :?代碼隨想錄Day34 LeetCode T343整數(shù)拆分 T96 不同的二叉搜索樹-CSDN博客 1.明白dp數(shù)組的含義 2.明白遞推公式的含義 3.初始化dp數(shù)組 4.注意dp數(shù)組的遍歷順序 5.打印dp數(shù)組排錯題目鏈接:1049. 最后一塊石頭的重量 II - 力扣（LeetCode）這題我們?nèi)匀徊捎脛右?guī)五部曲來寫,這題和
2024年02月06日
瀏覽(19)
2023華為OD機試真題Java【代表團坐車/動態(tài)規(guī)劃】【2023.Q2】
本題使用Java解答，如果需要python版本代碼，請參考以下鏈接： python代碼現(xiàn)在要舉行一場會議，有很多代表團參加。但是他們可能在同一個時間到達，而負(fù)責(zé)接待它們的接待處處只有一輛汽車，現(xiàn)在為了提高車輛利用率，請幫接待員計算可以坐滿車的接待方案，輸出方案數(shù)量
2024年02月15日
瀏覽(44)
華為OD機試 - 工作安排 - 動態(tài)規(guī)劃（Java 2023Q1 100分）
華為OD機試 2023B卷題庫瘋狂收錄中，刷題點這里小明每周上班都會拿著自己的工作
2024年02月13日
瀏覽(21)
華為OD機試 - 通過軟盤拷貝文件 - 動態(tài)規(guī)劃（Java 2023 B卷 200分）
華為OD機試 2023B卷題庫瘋狂收錄中，刷題點這里本專欄收錄于
2024年02月09日
瀏覽(23)