【算法思维】-- 动态规划(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++算法 —— 动态规划(3)多状态

    每一种算法都最好看完第一篇再去找要看的博客,因为这样会帮你梳理好思路,看接下来的博客也就更轻松了。当然,我也会尽量在写每一篇时都可以让不懂这个算法的人也能边看边理解。 动规的思路有五个步骤,且最好画图来理解细节,不要怕麻烦。当你开始画图,仔细阅

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

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

    2024年02月19日
    浏览(48)
  • C++算法 —— 动态规划(2)路径问题

    每一种算法都最好看完第一篇再去找要看的博客,因为这样会帮你梳理好思路,看接下来的博客也就更轻松了。当然,我也会尽量在写每一篇时都可以让不懂这个算法的人也能边看边理解。 动规的思路有五个步骤,且最好画图来理解细节,不要怕麻烦。当你开始画图,仔细阅

    2024年02月06日
    浏览(50)
  • 【动态规划】C++算法312 戳气球

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

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

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

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

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

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

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

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

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

    2024年01月16日
    浏览(52)
  • 【动态规划】【C++算法】2742. 给墙壁刷油漆

    【数位dp】【动态规划】【状态压缩】【推荐】1012. 至少有 1 位重复的数字 动态规划汇总 给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time ,分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠: 一位需要 付费 的油漆匠,刷第 i 堵墙需要花费 time[i] 单位

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

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

    2024年02月01日
    浏览(58)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包