【算法思维】-- 动态规划(C++)

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

OJ须知:

  • 一般而言,OJ在1s内能接受的算法时间复杂度:10e8 ~ 10e9之间(中值5*10e8)。在竞赛中,一般认为计算机1秒能执行 5*10e8 次计算
时间复杂度 取值范围
o(log2n) 大的离谱
O(n) 10e8
O(nlog(n)) 10e6
O(nsqrt(n))) 10e5
O(n^2) 5000
O(n^3) 300
O(2^n) 25
O(3^n) 15
O(n!)

11

时间复杂度排序: o(1) < o(log2n) < o(n) < o(nlog2n) < o(n^2) < o(n^3) < o(2^n) < o(2^n) < o(3^n) < o(n!)

目录

Dynamic Programming

DP定义

斐波那契数⭐

方法一:递归

复杂度分析

方法二:DP

复杂度分析

单词拆分⭐⭐

方法一:DP 

复杂度分析

三角形最小路径和⭐⭐

方法一:DP 

复杂度分析

方法二:DP(反向思维)

复杂度分析

不同路径⭐⭐

方法一:DP 

复杂度分析

最小路径和⭐⭐

方法一:DP 

复杂度分析

背包问题⭐⭐⭐

方法一:DP  

复杂度分析


Dynamic Programming

DP定义

        动态规划是分治思想的延伸,通俗一点来说就是大事化小,小事化了的艺术。

融汇贯通的理解:

        分治(大事化小,小事化了)将问题进行分解,通过求解子问题,再用子问题推导大问题得解。

        在将大问题化解为小问题的分治过程中,保存对这些小问题已经处理好的结果,并供后面处理更大规模的问题时直接使用这些结果。

DP具备了以下三个特点

  1. 分解子问题:把原来的问题分解成了几个相似的子问题(先求解最小的子问题)
  2. 求解子问题:所有的子问题都只需要解决一次
  3. 保存子问题的解:按照需要储存子问题的解。(后序再以此推动,从而以子问题的解求取更大的子问题的解)

融汇贯通的理解:

        DP VS 递归:递归中子问题的解一般是不保存的,而DP是需要保留结果的,有时候根据需要,有时候是部分的解,有时候甚至是保留全部的解。

动态规划的本质,是对问题状态的定义状态转移方程的定义(状态以及状态之间的递推关系)

融汇贯通的理解:

        状态的定义:子问题。

        状态转移方程的定义:用子问题推大问题。

动态规划问题一般从以下四个角度考虑:

  1. 状态定义(根据题目的问题抽象而出)
  2. 状态间的转移方程定义(根据题目的问题的线索 + 状态定义 = 得出(≈递归方程))
  3. 状态的初始化(一般就是最简单的子问题,不需要任何的推动,也不需要任何转移方程就可以将解确定出来)
  4. 返回结果(某一个状态的解 / 某几个状态处理的解)

状态定义的要求:定义的状态一定要形成递推关系

一句话概括:三特点四要素两本质。

难点:

  1. 状态比较抽象,不好寻找
  2. 转移方程根据线索不好找

适用场景:

  1. 最大值 / 最小值
  2. 可不可行 / 是不是
  3. 方案个数

斐波那契数⭐

509. 斐波那契数 - 力扣(LeetCode)

斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:

        F(0) = 0,F(1) = 1
        F(n) = F(n - 1) + F(n - 2),其中 n > 1

给定 n ,请计算 F(n) 。

提示:

  • 0 <= n <= 30。

方法一:递归

class Solution {
public:
	int Fib(int n) {
		// 初始值
		if (n == 0) return 0;
		if (n == 1 || n == 2) return 1;

		// F(n) = F(n-1) + F(n-2)
		return Fib(n - 1) + Fib(n - 2);
	}
};

复杂度分析

  • 时间复杂度:O(2^n),随着n的增大呈现指数增长,效率低下当输入比较大时,可能导致栈溢出在递归过程中有大量的重复计算。(此处:0 <= n <= 30侥幸跑过)
  • 空间复杂度:O(n),为树的高度。

下图以求n = 4为例:

【算法思维】-- 动态规划(C++)

        此处:1、根据C语言的函数栈帧开辟销毁特性2、根据C语言语句执行先左后右的顺序。在语句:

return Fib(n - 1) + Fib(n - 2);

        是先一路递归Fib(n - 1)后产生返回值并释放,才会再执行Fib(n - 2)。所以空间复杂度为树高:O(n)。

方法二:DP

引入DP四点:

  1. 状态定义(根据题目的问题抽象而出)
  2. 状态间的转移方程定义(根据题目的问题的线索 + 状态定义 = 得出(≈递归方程))
  3. 状态的初始化(一般就是最简单的子问题,不需要任何的推动,也不需要任何转移方程就可以将解确定出来)
  4. 返回结果(某一个状态的解 / 某几个状态处理的解)

抽象题中线索:

  • 状态定义:F(i) = ?
  • 状态间的转移方程定义:F(i) = F(i - 1) + F(i - 2)
  • 状态的初始化:F(0) = 0,F(1) = 1
  • 返回结果:F(n) = ?
class Solution {
public:
    int fib(int n) {
        vector<int> v(n + 1, 0);
        v[0] = 0;
        if(n >= 1) v[1] = 1; // 题目中允许n = 0
        for(int i = 2; i <= n; i++)
            v[i] = v[i - 1] + v[i - 2];
        return v[n];
    }
}

        经典的DP基础题,将每一个状态都进行保存,后面的状态都是通过前面已知状态结果,递推过来的。

复杂度分析

  • 时间复杂度:O(n)。
  • 空间复杂度:O(n)。

        此处还可以对空间复杂度进行优化,因为求当前状态只需要前两个状态的结果,其余结果毫无用处。

class Solution {
public:
    int fib(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        int F_one = 0, F_tow = 1;
        int ret = 0;
        for(int i = 2; i <= n; i++)
        {
            ret = F_one + F_tow;
        // 更新中间状态
            F_one = F_tow;
            F_tow = ret;
        }
        return ret;
    }
};
  • 时间复杂度:O(n)
  • 空间复杂度:O(1)

单词拆分⭐⭐

139. 单词拆分 - 力扣(LeetCode)


给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s 。

        s = "leetcode", wordDict = ["leet", "code"]

注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。

提示:

  • 1 <= s.length <= 300
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 20
  • s 和 wordDict[i] 仅有小写英文字母组成
  • wordDict中的所有字符串 互不相同

方法一:DP 

抽象题中线索:

  • 状态定义:s 的前 i 个字符是否可以被分割
  • 状态间的转移方程定义:s[0,n]能被分割,则s[n + 1,m]能否被分割,代表s[0,m]能否被分割(n < m)
  • 状态的初始化:空字符串true(没有任何实际意义,就是辅助)
  • 返回结果:s 是否可以被分割
class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        // 状态定义:s 的前 i 个字符是否可以被分割
        vector<bool> ret(s.size() + 1, false);
        // 状态的初始化:空字符串true
        ret[0] = true;
        unordered_set<string> dict;
        for(int i = 0; i < wordDict.size(); i++)
            dict.insert(wordDict[i]);

        // 状态间的转移方程定义: s[0,n]能被分割,则s[n + 1,m]能否被分割,代表s[0,m]能否被分割(n < m)
        for(int m = 1; m <= s.size(); m++)
        {
            for(int n = 0; n < m; n++)
            {
                if(ret[n] && dict.end() != dict.find(s.substr(n, m - n)))
                {
                    ret[m] = true;
                    break;
                }
            }
        }
        // 返回结果:s 是否可以被分割
        return ret[s.size()];
    }
};

复杂度分析

  • 时间复杂度:O(n^2)
  • 空间复杂度:O(n)

三角形最小路径和⭐⭐

​​​​​​120. 三角形最小路径和 - 力扣(LeetCode)


给定一个三角形 triangle ,找出自顶向下的最小路径和。

每一步只能移动到下一行中相邻的结点上。相邻的结点在这里指的是 下标上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标  i  或  i + 1

提示:

  • 1 <= triangle.length <= 200
  • triangle[0].length == 1
  • triangle[i].length == triangle[i - 1].length + 1
  • -104 <= triangle[i][j] <= 104

方法一:DP 

抽象题中线索:

  • 状态定义:从 [ 0, 0 ] 到 [ i, j ] 的min = ?
  • 状态间的转移方程定义:[ i, j ] += min([ i - 1, j - 1], [ i - 1, j ])(有些路径只有一条,代码里体现)

【算法思维】-- 动态规划(C++)

  • 状态的初始化:[ 0, 0 ]的min = [ 0, 0 ]
  • 返回结果:min ( [ 底行 ][ 0 ] ~ [ 底行 ][ 行底 ] )
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        if(triangle.empty())
            return 0;
        int row = triangle.size();
        int col = triangle[row - 1].size();

        // 状态定义:从[ 0, 0 ]到[ i, j ]的min = ?
        vector<vector<int>> ret(row, vector<int>(col, 0));

        // 状态的初始化: [ 0, 0 ]的min = [ 0, 0 ]
        ret[0][0] = triangle[0][0];
        for(int i = 1; i < row; i++)
        {
            for(int j = 0; j <= i; j++)
            {
                // 状态间的转移方程定义: [i, j] += min([i - 1, j - 1], [i - 1, j])
                if(j == 0) ret[i][j] = ret[i - 1][j] + triangle[i][j];
                else if(j == i) ret[i][j] = ret[i - 1][j - 1] + triangle[i][j];
                else ret[i][j] = min(ret[i - 1][j], ret[i - 1][j - 1]) + triangle[i][j];
            }
        }
        // 返回结果: min([底行][0] ~ [底行][行底])
        return *min_element(ret[row - 1].begin(), ret[row - 1].end());
    }
};

复杂度分析

  • 时间复杂度:O(n^2)是一个2、3、4、5、6、7、8 …… row + 1的等差数列。
  • 空间复杂度:O(n^2)

进阶:

        你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题吗?

        看上述代码,会发现我们根本就只是需要最后的一行数据,所以其实我们对于前述的二维数组,完全可以以一个以为数组代替。

class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        if(triangle.empty()) return 0;
        int row = triangle.size();
        int col = triangle[row - 1].size();

        // 状态定义:从[ 0, 0 ]到[ i, j ]的min = ?
        vector<int> ret(col, 0);

        // 状态的初始化: [ 0, 0 ]的min = [ 0, 0 ]
        ret[0] = triangle[0][0];
        for(int i = 1; i < row; i++)
        {
            for(int j = i; j >= 0; j--)
            {
                // 状态间的转移方程定义: [i, j] += min([i - 1, j - 1], [i - 1, j])
                if(j == 0) ret[j] = ret[j] + triangle[i][j];
                else if(j == i) ret[j] = ret[j - 1] + triangle[i][j];
                else ret[j] = min(ret[j], ret[j - 1]) + triangle[i][j];
            }
        }
        // 返回结果: min([底行][0] ~ [底行][行底])
        return *min_element(ret.begin(), ret.end());
    }
};
  • 时间复杂度:O(n^2),是一个2、3、4、5、6、7、8 …… row + 1的等差数列。
  • 空间复杂度:O(n)

方法二:DP(反向思维)

        前面我们利用的解法,是这一行的解来自上一行的解,而这次我们反着,这一行的解来自下一行的解而不是上一行的解。

抽象题中线索:

  • 状态定义:从 [ i, j ] 到 [ 底行, 行底 ] 的min = ?
  • 状态间的转移方程定义:[ i, j ] += min([ i + 1, j ], [ i + 1, j + 1 ])(有些路径只有一条,代码里体现)

【算法思维】-- 动态规划(C++)

  • 状态的初始化:[ 底行, 行底 ] 的 min = [ 底行, 行底 ]
  • 返回结果:[0, 0]
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        if(triangle.empty()) return 0;
        int row = triangle.size();
        int col = triangle[row - 1].size();
        vector<vector<int>> ret(row, vector<int>(col, 0));
        for(int i = 0; i<col; i++)
            ret[row - 1][i] = triangle[row - 1][i];

        for(int i = row - 2; i >= 0; i--)
        {
            for(int j = 0; j <= i; j++)
            {
                ret[i][j] = min(ret[i + 1][j], ret[i + 1][j + 1]) + triangle[i][j];
            }
        }
        return ret[0][0];
    }
};

复杂度分析

  • 时间复杂度:O(n^2)是一个2、3、4、5、6、7、8 …… row + 1的等差数列。
  • 空间复杂度:O(n^2)

不同路径⭐⭐

62. 不同路径 - 力扣(LeetCode)


一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为 “Start” )。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在下图中标记为 “Finish” )。

问总共有多少条不同的路径?

提示:

  • 1 <= m, n <= 100
  • 题目数据保证答案小于等于 2*10^9

方法一:DP 

抽象题中线索:

  • 状态定义:从 [0,0] 到 [i,j] 有几种路径?
  • 状态间的转移方程定义:[i,j] 路径 = [i,j - 1] 路径 +  [i - 1,j] 路径
  • 状态的初始化:第一行,第一列路径为1
  • 返回结果:[底行, 行底]
class Solution {
public:
    int uniquePaths(int m, int n) {
        // 状态定义: 从[0,0]到[i,j]有几种路径?
        vector<vector<int>> ret(m, vector<int>(n, 0));

        // 状态的初始化: 第一行,第一列路径为1
        for(int i = 0; i < m ; i++) ret[i][0] = 1;
        for(int i = 0; i < n ; i++) ret[0][i] = 1;

        for(int i = 1; i < m ; i++)
        {
            for(int j = 1; j < n; j++)
            {
                // 状态间的转移方程定义: [i,j]路径 = [i,j - 1]路径 + [i - 1,j]路径
                ret[i][j] = ret[i][j - 1] + ret[i - 1][j];
            }
        }

        // 返回结果: [底行, 行底]
        return ret[m - 1][n - 1];
    }
};

复杂度分析

  • 时间复杂度:O(m*n)。
  • 空间复杂度:O(m*n)。

进阶:

        你可以只使用 O(n) / O(m) 的额外空间来解决这个问题吗?

        我们通过上述代码可以发现,[i,j] 的路径数只和 [i - 1,j] 与  [i,j - 1] 有关。也就是说其实我们可以利用一个一维数组就解决问题。比如以列为一维数组:vector<int> array(m, 1),当列由第 i 列移动到 i + 1 列。

  • 状态定义:从 [0,0] 到 [i,j] 有几种路径?
  • 状态间的转移方程定义:[i] 路径(后) = [i - 1] 路径 +  [i] 路径(前)
  • 状态的初始化:第一列路径为1
  • 返回结果:[列底]
class Solution {
public:
    int uniquePaths(int m, int n) {
        // 状态定义: 从[0,0]到[i,j]有几种路径?
        // 状态的初始化: 第一列路径为1
        vector<int> ret(m, 1);

        for(int i = 1; i < n; i++)
        {
            for(int j = 1; j < m; j++)
            {
                // 状态间的转移方程定义: [i]路径(后) = [i - 1]路径 + [i]路径(前)
                ret[j] = ret[j - 1] + ret[j];
            }
        }

        // 返回结果: [列底]
        return ret[m - 1];
    }
};
  • 时间复杂度:O(m*n)。
  • 空间复杂度:O(m)。

最小路径和⭐⭐

64. 最小路径和 - 力扣(LeetCode)


给定一个包含非负整数的 m * n 网格 grid ,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明:每次只能向下或者向右移动一步。

提示:

  • m == grid.length
  • n == grid[ i ].length
  • 1 <= m, n <= 200
  • 0 <= grid[ i ][ j ] <= 100

方法一:DP 

抽象题中线索:

  • 状态定义:从 [0,0] 到 [i,j] min = ?
  • 状态间的转移方程定义:[i,j] += min ([i,j - 1],[i - 1,j])(有些路径只有一条,代码里体现)

【算法思维】-- 动态规划(C++)

  • 状态的初始化:[0, 0] min = [0, 0]
  • 返回结果:[底行, 行底]
class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int row = grid.size();
        int col = grid[0].size();
        // 状态定义: 从 [0,0] 到 [i,j] min = ?
        vector<vector<int>> ret(row, vector<int>(col, 0));
        
        // 状态的初始化: [0, 0] min = [0, 0]
        ret[0][0] = grid[0][0];

        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                // 状态间的转移方程定义: [i,j] += min ([i,j - 1],[i - 1,j])
                if(i == 0 && j > 0) ret[0][j] = grid[0][j] + ret[0][j - 1];
                else if(j == 0 && i > 0) ret[i][0] = grid[i][0] + ret[i - 1][0];
                else if(j > 0 && i > 0) ret[i][j] = min(ret[i][j - 1], ret[i - 1][j]) + grid[i][j];
            }
        }
        
        // 返回结果: [底行, 行底]
        return ret[row - 1][col - 1];
    }
};

        方便看原理,下述代码将状态间的转移方程特殊情况,单独提出进行书写。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int row = grid.size();
        int col = grid[0].size();
        // 状态定义: 从 [0,0] 到 [i,j] min = ?
        vector<vector<int>> ret(row, vector<int>(col, 0));

        // 状态的初始化: [0, 0] min = [0, 0]
        ret[0][0] = grid[0][0];

        // 特殊转换状态:第一行、第一列
        for(int i = 1; i < row; i++) ret[i][0] = grid[i][0] + ret[i - 1][0];
        for(int i = 1; i < col; i++) ret[0][i] = grid[0][i] + ret[0][i - 1];

        for(int i = 1; i < row; i++)
        {
            for(int j = 1; j < col; j++)
            {
                // 状态间的转移方程定义: [i,j] += min ([i,j - 1],[i - 1,j])
                ret[i][j] = min(ret[i][j - 1], ret[i - 1][j]) + grid[i][j];
            }
        }
        // 返回结果: [底行, 行底]
        return ret[row - 1][col - 1];
    }
};

复杂度分析

  • 时间复杂度:O(m*n)。
  • 空间复杂度:O(m*n)。

进阶:

        你可以只使用 O(n) / O(m) 的额外空间来解决这个问题吗?

        此题与上一题极为的相似,所上一题采取的列解决,这一题就采取行解决。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int row = grid.size();
        int col = grid[0].size();
        // 状态定义: 从 [0,0] 到 [i,j] min = ?
        vector<int> ret(col, 0);
        
        // 状态的初始化: [0, 0]min = [0, 0]
        ret[0] = grid[0][0];

        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                // 状态间的转移方程定义: [j] = min ([j],[j-1]) + grid[i][j]
                if(i == 0 && j > 0) ret[j] = ret[j - 1] + grid[i][j];
                else if(j == 0 && i > 0) ret[j] = ret[j] + grid[i][j];
                else if(i > 0 && j > 0)ret[j] = min(ret[j - 1], ret[j]) + grid[i][j];
            }
        }

        // 返回结果: [底行, 行底]
        return ret[col - 1];
    }
};
  • 时间复杂度:O(m*n)。
  • 空间复杂度:O(n)。

背包问题⭐⭐⭐

125 · 背包问题(二) - LintCode


有 n 个物品和一个大小为 m 的背包,给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值。

问最多能装入背包的总价值是多大?

提示:

  1. A[i], V[i], n, m 均为整数
  2. 你不能将物品进行切分
  3. 你所挑选的要装入背包的物品的总大小不能超过 m
  4. 每个物品只能取一次
  5. m <= 1000len(A),len(V)<=100

方法一:DP  

抽象题中线索:

  • 状态定义:到第 i 商品的第 j 个空间 ret[i][j] 时的max价值 = ?
  • 状态间的转移方程定义:
  1. 当前空间 j 不够放该商品,原封不动(上次商品的样子)ret[i][j] = ret[i - 1][j] 
  2. 当前空间 j 够放该商品max( (放入i + 剩余空间能放的max) , (前面 i-1) )ret[i][j] = max(ret[i - 1][j],v[i - 1] + ret[i - 1][j - a[i - 1]]) 

【算法思维】-- 动态规划(C++)

【算法思维】-- 动态规划(C++)

  • 状态的初始化:没有商品 ret[0][j]max价值 = 0,没有空间 ret[i][0]max价值 = 0
  • 返回结果:到第 最后 商品的第 最后 空间 ret[最后][最后] 时的max价值 = ?
class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param a: Given n items with size A[i]
     * @param v: Given n items with value V[i]
     * @return: The maximum value
     */
    int backPackII(int m, vector<int> &a, vector<int> &v) {
        // write your code here
        // 状态定义: 到第 i 商品的第 j 个空间 ret[i][j] 时的max价值 = ?
        // ​​​​​​​状态的初始化: 没有商品 ret[0][j]max价值 = 0,没有空间 ret[i][0]max价值 = 0
        vector<vector<int>> ret(a.size() + 1, vector<int>(m + 1, 0));

        // 状态间的转移方程定义: 
        for(int i = 1; i <= a.size(); i++)
        {
            for(int j = 1; j <= m; j++)
            {
                // 当前空间 j 不够放该商品,原封不动(上次商品的样子): ret[i][j] = ret[i - 1][j] 
                if(a[i - 1] > j)
                    ret[i][j] = ret[i - 1][j];
                // 当前空间 j 够放该商品( max( (放入i + 剩余空间能放的max) , (前面 i-1) ) ): ret[i][j] = max(ret[i - 1][j],v[i - 1] + ret[i - 1][j - a[i - 1]]) 
                else
                    ret[i][j] = max(ret[i - 1][j], v[i - 1] + ret[i - 1][j - a[i - 1]]);
            }
        }
        // 返回结果: 到第 最后 商品的第 最后 空间 ret[最后][最后] 时的max价值 = ?
        return ret[a.size()][m];
    }
};

复杂度分析

(m:背包大小;n:商品个数)

  • 时间复杂度:O(m*n)。
  • 空间复杂度:O(m*n)。

进阶:

        你可以只使用 O(m) 的额外空间来解决这个问题吗?

        我们可以发现,我们使用的仅仅就是 i -1 个商品时和 i 个商品时背包的状态。所我们可以将 m*n 变为 m*2,即:O(m)。

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param a: Given n items with size A[i]
     * @param v: Given n items with value V[i]
     * @return: The maximum value
     */
    int backPackII(int m, vector<int> &a, vector<int> &v) {
        // write your code here
        // 状态定义: 
        // ​​​​​​​状态的初始化: 
        vector<vector<int>> ret(2, vector<int>(m + 1, 0));

        // 最后一组数据
        int row = 0;
        // 状态间的转移方程定义: 
        for(int i = 1; i <= a.size(); i++)
        {
            for(int j = 1; j <= m; j++)
            {
                row = i % 2;
                if(a[i - 1] > j)
                    ret[row][j] = ret[(row + 1)%2][j];
                else
                    ret[row][j] = max(ret[(row + 1)%2][j], v[i - 1] + ret[(row + 1)%2][j - a[i - 1]]);
            }
        }
        // 返回结果: 
        return ret[row][m];
    }
};

核心:

  • row = i % 2 是当前行
  • (row + 1) % 2 是上一行

待更……文章来源地址https://www.toymoban.com/news/detail-431065.html

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

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

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

相关文章

  • 【动态规划】C++算法312 戳气球

    视频算法专题 动态规划汇总 有 n 个气球,编号为0 到 n - 1,每个气球上都标有一个数字,这些数字存在数组 nums 中。 现在要求你戳破所有的气球。戳破第 i 个气球,你可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。 这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果

    2024年02月03日
    浏览(41)
  • C++动态规划-线性dp算法

    莫愁千里路 自有到来风 CSDN 请求进入专栏                                    X 是否进入《 C++ 专栏》? 确定 目录  线性dp简介 斐波那契数列模型  第N个泰波那契数 思路: 代码测试:  三步问题 思路: 代码测试: 最小花费爬楼梯 思路: 代码测试:  路径问题 数字三

    2024年02月19日
    浏览(46)
  • 【动态规划】C++算法:403.青蛙过河

    视频算法专题 动态规划汇总 一只青蛙想要过河。 假定河流被等分为若干个单元格,并且在每一个单元格内都有可能放有一块石子(也有可能没有)。 青蛙可以跳上石子,但是不可以跳入水中。 给你石子的位置列表 stones(用单元格序号 升序 表示), 请判定青蛙能否成功过

    2024年01月17日
    浏览(47)
  • 【动态规划】C++算法:最长有效括号

    视频算法专题 动态规划汇总 给你一个只包含 ‘(’ 和 ‘)’ 的字符串,找出最长有效(格式正确且连续)括号子串的长度。 示例 1: 输入:s = “(()” 输出:2 解释:最长有效括号子串是 “()” 示例 2: 输入:s = “)()())” 输出:4 解释:最长有效括号子串是 “()()” 示例

    2024年02月01日
    浏览(56)
  • 【动态规划】【数学】【C++算法】18赛车

    视频算法专题 动态规划汇总 数学 你的赛车可以从位置 0 开始,并且速度为 +1 ,在一条无限长的数轴上行驶。赛车也可以向负方向行驶。赛车可以按照由加速指令 ‘A’ 和倒车指令 ‘R’ 组成的指令序列自动行驶。 当收到指令 ‘A’ 时,赛车这样行驶: position += speed speed

    2024年01月19日
    浏览(45)
  • c++ 算法之动态规划—— dp 详解

    dp 是 c++ 之中一个简单而重要的算法,每一个 OIer 必备的基础算法,你知道它究竟是什么吗? 目录 一、简介         1.为什么不能贪心?         2.揭秘 dp   二、应用         1.定义         2.边界值         3.动态转移方程         4.结果         5.代码

    2024年04月09日
    浏览(46)
  • C++算法之动态规划(ACWING题目)

    动态规划时间复杂度:状态数量*转移计算量 线性DP 一.数字三角形 动态规划:     1.状态表示:         集合:f[i, j]表示所有从起点走到(i, j)的路径         属性:所有路径上的数字之和的最大值     2.状态计算:         如何得到f[i, j]?             从左边路径走到和

    2024年02月20日
    浏览(39)
  • 【动态规划】【 数学】C++算法:514自由之路

    视频算法专题 动态规划汇总 数学 电子游戏“辐射4”中,任务 “通向自由” 要求玩家到达名为 “Freedom Trail Ring” 的金属表盘,并使用表盘拼写特定才能开门。 给定一个字符串 ring ,表示刻在外环上的编码;给定另一个字符串 key ,表示需要拼写的。您需要算

    2024年01月16日
    浏览(51)
  • 【动态规划】【C++算法】639 解码方法 II

    视频算法专题 动态规划汇总 字符串 滚动向量 一条包含字母 A-Z 的消息通过以下的方式进行了 编码 : ‘A’ - “1” ‘B’ - “2” … ‘Z’ - “26” 要 解码 一条已编码的消息,所有的数字都必须分组,然后按原来的编码方案反向映射回字母(可能存在多种方式)。例如,“

    2024年01月18日
    浏览(46)
  • 【动态规划】 【字典树】C++算法:472 连接词

    视频算法专题 动态规划汇总 字典树 给你一个 不含重复 单词的字符串数组 words ,请你找出并返回 words 中的所有 连接词 。 连接词 定义为:一个完全由给定数组中的至少两个较短单词(不一定是不同的两个单词)组成的字符串。 示例 1: 输入:words = [“cat”,“cats”,“cat

    2024年02月01日
    浏览(57)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包