2023-05-02 动态规划简介

这篇具有很好参考价值的文章主要介绍了2023-05-02 动态规划简介。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

动态规划简介

1 动态规划的基本概念

阶段、状态、决策、策略、状态转移方程

1) 阶段和阶段变量

  • 将问题的全过程恰当地分成若干个相互联系的阶段闫氏DP分析法:对应f[i][j]的ij遍历时形成的所有f[i][j]
  • 阶段的划分一般根据时间和空间的自然特征去划分
  • 阶段的划分便于把问题转化成多阶段决策问题

2) 状态和状态变量

  • 通常一个阶段包含若干状态

    闫氏DP分析法:每个阶段分多种情况

  • 状态可由变量来描述

3) 决策、决策变量和决策允许集合

  • 决策:在对问题的处理中作出的每种选择性的行动闫氏DP分析法:对应状态计算

    即从该阶段的每一个状态出发,通过一次选择性的行动转移至下一阶段的相应状态对应闫氏DP分析法:即状态转移

  • 决策变量:一个实际问题可能需要有多次决策和多个决策点,在每个阶段每个状态中都需要有一次决策,决策可以用变量来描述,称这种变量为决策变量

  • 决策允许集合:在实际问题中,决策变量的取值范围

4) 策略和最优策略

对应闫式DP分析法的"属性:max、min、cnt"

  • 策略:所有阶段依次排列构成问题的全过程,全过程中各阶段决策变量所组成的有序总体称为策略

    策略一般对应实际问题的一种解。简单说就是每个阶段选一个状态按照某种决策规律连起来组成的一条链路

  • 最优策略:在实际问题中,从允许决策集合中找出最优效果的策略称为最优策略

    最优策略一般对应实际问题的最优解,这个也是大部分DP题目的目标

以数塔问题为例,举例如下:
2023-05-02 动态规划简介

5) 状态转移方程

上个阶段状态到下个阶段状态的决策规律

  • 前一阶段的终点的就是后一阶段的起点
  • 对前一阶段的状态做出某种决策,产生后一种阶段的状态
  • 这种关系描述了从i阶段到i+1阶段的演变规律,称为状态转移方程

即从dp[i]到dp[i+1]的计算公式

2023-05-02 动态规划简介

6) 举例

2023-05-02 动态规划简介

  • 1.阶段:长条
  • 2.状态:小圆圈
  • 3.决策:长条内的小圆圈转移到下一个长条内的小圆圈

    决策集合就是所有的转移可能,即图中的箭头

  • 4.策略:从第一个长条(阶段)到最后一个长条,每个长条选一个状态(小圆圈)用箭头(决策)连接起来的一条链路

    最优策略就是所有策略中满足最值的一条链路(最大值max、最小值min、计数cnt、是否存在exist的等)

  • 5.状态转移方程:从上一个状态到下一个状态的转移方程式,按照这个方程式得到的策略就是最优策略

结合上面总结的5个概念,来尝试解决两个问题

举例1:从n个数的数组 a [ n ] a[n] a[n]中取出k个数,使得他们的和最大

f [ i ] [ j ] f[i][j] f[i][j]表示从第1个数到第i个数之间,已经选取了j个数,其和最大的值

  • 阶段阶段[i](即 f [ i ] f[i] f[i])指前i个数组成的序列
  • 状态:j,即前i个数中选取了j个数, 0 ≤ j ≤ i 0≤j≤i 0ji
  • 决策:可选的决策集合如下,第i个数表示前i个数的最后一个数,闫氏分析法叫"最后一个不同点"
    • A. 第 i 个数 a [ i ] 第i个数a[i] i个数a[i]到最终的j个数中:   f [ i ] [ j ] = f [ i − 1 ] [ j − 1 ] + f [ i ] f[i][j] = f[i - 1][j - 1] + f[i] f[i][j]=f[i1][j1]+f[i]
    • B.不取 第 i 个数 a [ i ] 第i个数a[i] i个数a[i]到最终的j个数中: f [ i ] [ j ] = f [ i − 1 ] [ j ] f[i][j] = f[i - 1][j] f[i][j]=f[i1][j]
  • 策略:使得f[i][j]尽量大,即取决策A和B的较大者

    对应闫氏分析法的max

  • 状态转移方程:满足最优策略的方程,即 f [ i ] [ j ] = m a x { a [ i ] + f [ i − 1 ] [ j − 1 ] , f [ i − 1 ] [ j ] } f[i][j] = max\lbrace a[i] + f[i - 1][j - 1], f[i - 1][j]\rbrace f[i][j]=max{a[i]+f[i1][j1],f[i1][j]}
举例2:从n个数的数组a[n]中找出最长上升子序列的元素个数

f[i]表示[a[0]~a[i]]组成的序列中且最后一个数是a[i]的最长上升子序列的长度

  • 阶段阶段[i](即 f [ i ] f[i] f[i])指前i+1个数组成的序列,注意下标从0开始
  • 状态:i前面某个位置j处的数a[j],作为最长上升子序列的前一个值(因为a[i]必须是最长上升子序列的最后一个值)

    阶段内的多个状态就是指j在范围 0 ≤ j < i 0≤j<i 0j<i内取变所有值的对应a[j]

  • 决策:根据a[j]是否小于a[i],决定a[j]是否在以a[i]结尾的上升子序列中
    • a [ j ] < a [ i ] a[j] < a[i] a[j]<a[i]: 满足最长上升子序列要求,即a[j]在以a[i]结尾的上升子序列中,所以更新以a[i]结尾的最长子序列长度 f [ i ] = m a x { f [ i ] , f [ j ] + 1 ∣ 0 ≤ j < i } f[i] = max\lbrace f[i], f[j] + 1 \mid 0≤j<i\rbrace f[i]=max{f[i],f[j]+10j<i}
    • a [ j ] > = a [ i ] a[j] >= a[i] a[j]>=a[i]:不满足最长上升子序列的要求,即a[j]不在以a[i]结尾的上升子序列中,不更新以a[i]结尾的最长子序列长度,直接跳过即可
  • 策略:在 0 ≤ j < i 0≤j<i 0j<i范围内,不断根据a[j]的值刷新f[i],获取f[i]的最大值
  • 状态转移方程 f [ i ] = m a x { f [ i ] , f [ j ] + 1 ∣ 0 ≤ j < i } f[i] = max\lbrace f[i], f[j] + 1 \mid 0≤j<i\rbrace f[i]=max{f[i],f[j]+10j<i}

题目见:300. 最长上升子序列

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

        int N = a.size();
        // f[i]表示[a[0]~a[i]]组成的序列中且最后一个数是a[i]的最长上升子序列的长度
        vector<int> f(N, 1); // 初始化一个都为1的二维数组,即每个元素至少自己都是一个上升子序列
        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 动态规划的性质

动态规划适用的问题需要满足的条件?

什么样的"多阶段决策问题"才可以用动态规划的方法来求解呢?前提是能划分阶段,然后必须满足下面两个条件

  • 1) 最优化原理

    作为整个过程的最优策略,具有:无论过去的状态和策略如何,对前面的决策所形成的状态而言,余下的所有决策必须构成最优策略的性质,即

    • 子问题的局部最优会促成整个问题的全局最优
    • 问题具有最优子结构的性质
    • 一个问题的最优解只取决于其子问题的最优解
  • 2) 无后效性原则
    • 某阶段的状态一旦确定,则此后过程的演变不再受此前各状态及决策的影响,即“未来与过去无关"
    • 当前的状态是此前历史的一个完整的总结,此前的历史只能通过当前的状态去影响过程在未来的演变,即"未来只会被现在影响

不能用动态规划来做的题

误用动态规划会得到错误的结果

  • 对于不能划分阶段的题,不能用动态规划来解
  • 不符合最优化原理,不能用动态规划来解
  • 不具备无后效性原则的,不能用动态规划来解

动态规划的设计方法

  • 正推:从初始状态开始,通过对中间阶段的决策的选择,达到结束状态,我们也称递推
  • 倒推:从结束状态开始,通过对中间阶段的决策的选择,达到开始状态。我们可以把这种方法看成记忆化搜索

动态规划设计方法的一般模式

1和2相当于闫氏DP分析法的确定集合(即明确f[i][j]的含义,即状态表示);3相当于闫氏DP分析法里的状态计算,即确定每个阶段的所有转移可能情况,然后获取目标的属性值(max、min、cnt等)

  • 1)划分阶段
  • 2)确定状态和状态变量

    一般是确定f[i][j]中j的定义(即状态)和范围(如 a ≤ j < b a≤j<b aj<b即状态变量)

  • 3)确定决策并写出状态转移方程

    按照f[i][j]中i的定义确定决策集合,根据目标属性(max、min、cnt、存在等)得出状态转移方程

  • 4)寻找边界条件

    根据题目给出的变量范围,小心带入状态变量和决策集合的值到状态转移方程中,得到最终的目标属性值

  • 5)设计并实现程序

    写好、实现好1~4的步骤对应的代码,并通过一些动态规划的优化技巧进行性能提升

3 动态规划与记忆化搜索

记忆化搜索的概念

实现一个函数,用"搜索"的方式实现DP的更新,通常用于解决状态转移顺序不方便人为确定的DP

例题:AcWing898:数字三角形

题目大意:

输入一个n层的三角形,第i层有i个数,求从第1层到第n层的所有路线中,权值之和最大的路线。
规定:第i层的某个数只能连线走到第i+1层中与它位置相邻的两个数中的一个。

普通递归实现,会超时,给的例子进入递归217次
/**
 * 数塔问题
 * https://www.acwing.com/problem/content/900/
 */

#include <iostream>
#include <vector>

using namespace std;

#define INF 0x3f3f3f3f

/**
 * 分解为最优子结构问题,先求局部最优解
 * @param i 第i行(下标从0开始)
 * @param j 第j列(下标从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); // 决策集合只有右上元素
    }
}

/**
 * 统计最后一行的所有子问题最优解,其中最大的就是最终结果
 * @param nums 存储三角形的数组
 * @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)); // 二维数组初始化为很大的数,防止干扰数据判断
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) {
            cin >> v[i][j];
        }
    }
    cout << Solve(v) << endl;
    return 0;
}
记忆化搜索,虽然提高了效率,进入递归次数变成了87次,但是仍然超时
/**
 * 数塔问题
 * https://www.acwing.com/problem/content/900/
 */

#include <iostream>
#include <vector>

using namespace std;

#define INF 0x3f3f3f3f

/**
 * 分解为最优子结构问题,先求局部最优解
 * @param i 第i行(下标从0开始)
 * @param j 第j列(下标从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];
}

/**
 * 统计最后一行的所有子问题最优解,其中最大的就是最终结果
 * @param nums 存储三角形的数组
 * @return 最大的路径和
 */
int Solve(vector<vector<int>> &nums) {
    int res = -INF;
    int n = nums.size();
    vector<vector<int>> dp(n, vector<int>(n, -INF)); // 记忆数组,初始化为最小值
    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)); // 二维数组初始化为很大的数,防止干扰数据判断
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) {
            cin >> v[i][j];
        }
    }
    cout << Solve(v) << endl;
    return 0;
}
动态规划实现,唯一不超时的实现
/**
 * 数塔问题
 * https://www.acwing.com/problem/content/900/
 */

#include <iostream>
#include <vector>

#define INF 0x3f3f3f3f

using namespace std;

/**
 * 统计最后一行的所有子问题最优解,其中最大的就是最终结果
 * @param nums 存储三角形的数组
 * @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++) { // 状态(变量)
            // 决策
            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)); // 二维数组初始化为很大的数,防止干扰数据判断
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= i; j++) {
            cin >> v[i][j];
        }
    }
    cout << Solve(v) << endl;
    return 0;
}
本问题的动态规划浅析

d p [ i ] [ j ] dp[i][j] dp[i][j]表示第i行第j列对应的最长路径和

  • 阶段 d p [ i ] dp[i] dp[i]即第i行,每行为一个阶段
  • 状态 d p [ i ] [ j ] dp[i][j] dp[i][j]第j列,状态变量为j,其取值范围为 0 ≤ j ≤ i 0≤j≤i 0ji
  • 决策:决策为当前状态dp[i][j]从哪个状态转移过来(不同的转移点即为决策集合),分析题目可知可选的决策集合如下
    • A.从左上角转移过来: d p [ i ] [ j ] = n u m s [ i ] [ j ] + d p [ i − 1 ] [ j − 1 ] dp[i][j] = nums[i][j] + dp[i - 1][j - 1] dp[i][j]=nums[i][j]+dp[i1][j1]
    • B.从右上角转移过来: d p [ i ] [ j ] = n u m s [ i ] [ j ] + d p [ i − 1 ] [ j ] dp[i][j] = nums[i][j] + dp[i - 1][j] dp[i][j]=nums[i][j]+dp[i1][j]
  • 策略:最优策略是使得dp[i][j]尽量大,即取决策A和B的较大者

    对应闫氏分析法的max

  • 状态转移方程:满足最优策略的方程,即 d p [ i ] [ j ] = m a x { n u m s [ i ] [ j ] + d p [ i − 1 ] [ j − 1 ] , n u m s [ i ] [ j ] + d p [ i − 1 ] [ j ] } dp[i][j] = max\lbrace nums[i][j] + dp[i - 1][j - 1], nums[i][j] + dp[i - 1][j]\rbrace dp[i][j]=max{nums[i][j]+dp[i1][j1],nums[i][j]+dp[i1][j]},提取出 n u m s [ i ] [ j ] nums[i][j] nums[i][j]得到 d p [ i ] [ j ] = n u m s [ i ] [ j ] + m a x { d p [ i − 1 ] [ j − 1 ] , d p [ i − 1 ] [ j ] } dp[i][j] = nums[i][j] + max\lbrace dp[i - 1][j - 1], dp[i - 1][j]\rbrace dp[i][j]=nums[i][j]+max{dp[i1][j1],dp[i1][j]}
  • 边界条件:注意左上角点或右上角点不存在的情况,区分三种情况计算 d p [ i ] [ j ] dp[i][j] dp[i][j]

例题:AcWing901:滑雪

该题不能用动态规划做,因为没法划分状态

纯递归,会超时

累计进入递归912次

/**
 * 滑雪:不好划分阶段,只能用记忆化搜索做,不能用动态规划做
 * 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是因为当前点(r, c)也算一个距离
}

int main() {
    /** 1.初始化数据 */
    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)); // 访问数据重新初始化
            res = max(res, solve(r, c));
        }
    }
    cout << res << endl;
    return 0;
}
记忆数组,仍然超时

累计进入递归65次

/**
 * 滑雪:不好划分阶段,只能用记忆化搜索做,不能用动态规划做
 * 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是因为当前点(r, c)也算一个距离
    return dp[r][c];
}

int main() {
    /** 1.初始化数据 */
    cin >> R >> C;
    grid.resize(R, vector<int>(C, 0));
    dp.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(); // 如果之前赋值过,重新resize前务必记得clear一下,否则之前的数据仍然会存在
            visited.resize(R, vector<bool>(C, false)); // 访问数据重新初始化
            res = max(res, solve(r, c));
        }
    }
    cout << res << endl;
    return 0;
}
记忆数组,去掉访问数组,通过

看来访问数组还挺耗性能呀

/**
 * 滑雪:不好划分阶段,只能用记忆化搜索做,不能用动态规划做
 * 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) { // 遍历过直接返回了,起到了访问数组的作用
        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是因为当前点(r, c)也算一个距离
    return dp[r][c];
}

int main() {
    /** 1.初始化数据 */
    cin >> R >> C;
    grid.resize(R, vector<int>(C, 0));
    dp.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++) {
            res = max(res, solve(r, c));
        }
    }
    cout << res << endl;
    return 0;
}
本问题不能用动态规划来做的原因浅析

因为状态转移顺序不方便人为确定,所以此题不能用动态规划来做。下面按照动态规划的步骤进行分析

dp[i][j]表示第i行第j列的元素作为起点开始滑雪,能滑的最远距离

  • 阶段 d p [ i ] dp[i] dp[i]即第i行,每行为一个阶段

  • 状态 d p [ i ] [ j ] dp[i][j] dp[i][j]第j列,状态变量为j,其取值范围为 0 ≤ j < C 0≤j<C 0jC

  • 决策:决策为当前状态dp[i][j]从哪个状态转移过来(不同的转移点即为决策集合),分析题目可知可选的决策集合如下(假设满足题目要求的其他限制条件地前提下,如必须高度递减往下滑和不能出边界等)

    • A.从左边转移过来: d p [ i ] [ j ] = g r i d [ i ] [ j − 1 ] + 1 dp[i][j] = grid[i][j - 1] + 1 dp[i][j]=grid[i][j1]+1
    • B.从右边转移过来: d p [ i ] [ j ] = g r i d [ i ] [ j + 1 ] + 1 dp[i][j] = grid[i][j + 1] + 1 dp[i][j]=grid[i][j+1]+1
    • C.从上面转移过来: d p [ i ] [ j ] = g r i d [ i − 1 ] [ j ] + 1 dp[i][j] = grid[i - 1][j] + 1 dp[i][j]=grid[i1][j]+1
    • D.从下面转移过来: d p [ i ] [ j ] = g r i d [ i + 1 ] [ j ] + 1 dp[i][j] = grid[i + 1][j] + 1 dp[i][j]=grid[i+1][j]+1

    从上面四种决策可知,要得到dp[i][j],必须要先计算出i+1、i-1、j+1、j-1四种状态对应的值,但是dp中的for循环都是单向递增或递减的,不可能同时算出i前面和后面j前面和后面的状态值,因此这四种决策无法同时得到,因此也就没有下面的最优策略计算了,故动态规划不能用了文章来源地址https://www.toymoban.com/news/detail-435359.html

到了这里,关于2023-05-02 动态规划简介的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 动态规划02-斐波那契类型二

    给你一个整数数组 cost ,其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用,即可选择向上爬一个或者两个台阶。 你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。 请你计算并返回达到楼梯顶部的最低花费。 真题点击此处:746.使用最小花费爬楼

    2024年01月16日
    浏览(40)
  • Day36算法记录|动态规划 dp02

    步骤回顾: C语言版本写的很清楚 对应得Java版本视频解析 方法一: 动态规划 1 确定dp数组(dp table)以及下标的含义 dp[i][j] :表示从(0 ,0)出发,到(i, j) 有dp[i][j]条不同的路径。 2 . 确定递推公式 ,求dp[i][j],只能有两个方向来推导出来,即dp[i - 1][j] 和 dp[i][j - 1]。 3. dp数

    2024年02月12日
    浏览(49)
  • 【算法】动态规划 ① ( 动态规划简介 | 自底向上的动态规划示例 | 自顶向下的动态规划示例 )

    动态规划 , 英文名称 Dynamic Programming , 简称 DP , 不是具体的某种算法 , 是一种算法思想 ; 具体的算法都有具体的步骤 , 如 : 二分法 , 其 有固定的解决步骤 , 先取一个中心点 , 判断解在左边还是右边 , 然后在一边再取一个中心点 , 再进行判定 , 该算法有具体的步骤 ; 动态规划

    2024年01月16日
    浏览(45)
  • Day43|动态规划part05: 1049. 最后一块石头的重量 II、494. 目标和、474. 一和零

    本题物品的重量为stones[i],物品的价值也为stones[i]。 对应着01背包里的物品重量weight[i]和 物品价值value[i]。 确定dp数组以及下标的含义 dp[j]表示容量(这里说容量更形象,其实就是重量)为j的背包,最多可以背最大重量为dp[j] 。 确定递推公式 01背包的递推公式为:dp[j] = ma

    2024年04月23日
    浏览(47)
  • 动态规划机试2023.4.19

    eg12.1 N阶楼梯上楼问题 ex12.1 吃糖果和(eg12.1的程序一模一样) eg12.2 最大序列和 eg12.3 最大子矩阵(北京大学复试上机题) 复习了二维前缀和并且使用暴力做法解出该题 ex12.2 最大连续子序列(浙江大学复试上机题) 使用前缀和 eg12.4 拦截导弹(北京大学复试上机题) 最大不

    2023年04月22日
    浏览(27)
  • 【LeetCode题目详解】第九章 动态规划 part05 1049. 最后一块石头的重量 II 494. 目标和 474.一和零(day43补)

    有一堆石头,用整数数组  stones 表示。其中  stones[i] 表示第 i 块石头的重量。 每一回合,从中选出 任意两块石头 ,然后将它们一起粉碎。假设石头的重量分别为  x 和  y ,且  x = y 。那么粉碎的可能结果如下: 如果  x == y ,那么两块石头都会被完全粉碎; 如果  x != y

    2024年02月09日
    浏览(36)
  • 代码随想录Day36 动态规划05 LeetCode T1049最后一块石头的重量II T494 目标和 T474 一和零

    理论基础  : 代码随想录Day34 LeetCode T343整数拆分 T96 不同的二叉搜索树-CSDN博客 1.明白dp数组的含义 2.明白递推公式的含义 3.初始化dp数组 4.注意dp数组的遍历顺序 5.打印dp数组排错 题目链接:1049. 最后一块石头的重量 II - 力扣(LeetCode) 这题我们仍然采用动规五部曲来写,这题和

    2024年02月06日
    浏览(40)
  • 2023华为OD机试真题Java【代表团坐车/动态规划】【2023.Q2】

    本题使用Java解答,如果需要python版本代码,请参考以下链接: python代码 现在要举行一场会议,有很多代表团参加。但是他们可能在同一个时间到达,而负责接待它们的接待处处只有一辆汽车,现在为了提高车辆利用率,请帮接待员计算可以坐满车的接待方案,输出方案数量

    2024年02月15日
    浏览(108)
  • 华为OD机试 - 通过软盘拷贝文件 - 动态规划(Java 2023 B卷 200分)

    华为OD机试 2023B卷题库疯狂收录中,刷题 点这里 本专栏收录于

    2024年02月09日
    浏览(40)
  • 华为OD机试 - 工作安排 - 动态规划(Java 2023Q1 100分)

    华为OD机试 2023B卷题库疯狂收录中,刷题 点这里 小明每周上班都会拿着自己的工作

    2024年02月13日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包