【算法思维】-- 动态规划

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

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为例:

【算法思维】-- 动态规划

        此处: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 ])(有些路径只有一条,代码里体现)

【算法思维】-- 动态规划

  • 状态的初始化:[ 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 ])(有些路径只有一条,代码里体现)

【算法思维】-- 动态规划

  • 状态的初始化:[ 底行, 行底 ] 的 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])(有些路径只有一条,代码里体现)

【算法思维】-- 动态规划

  • 状态的初始化:[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]]) 

【算法思维】-- 动态规划

【算法思维】-- 动态规划

  • 状态的初始化:没有商品 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-451770.html

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

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

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

相关文章

  • 力扣第96题 不同的二叉搜索树 c++ 二叉搜索树 动态规划 + 数学思维

    96. 不同的二叉搜索树 中等 相关标签 树   二叉搜索树   数学   动态规划   二叉树 给你一个整数  n  ,求恰由  n  个节点组成且节点值从  1  到  n  互不相同的  二叉搜索树  有多少种?返回满足题意的二叉搜索树的种数。 示例 1: 示例 2: 提示: 1 = n = 19 vectorint

    2024年02月06日
    浏览(35)
  • 山东大学计算机科学与技术学院程序设计思维与实践作业 week14-动态规划(4)

    山东大学计算机科学与技术学院程序设计思维与实践作业 山大程序设计思维与实践作业 sdu程序设计思维与实践 山东大学程序设计思维实践作业H14 山大程序设计思维实践作业H14 山东大学程序设计思维与实践 week14-动态规划(4) 相关资料:GitHub 题目描述 给出一棵树,求树的

    2024年02月09日
    浏览(129)
  • 【算法】动态规划 ⑧ ( 动态规划特点 )

    求解类型 : 动态规划 必须是求 最值 , 可行性 , 方案数 , 三者之一 , 如果求其它内容 , 则不能使用动态规划算法 ; 求最值 : 最大值 , 最小值 等 ; 大规模问题的结果 由 小规模问题 的计算结果 取最大值 大规模问题的结果 由 小规模问题 的计算结果 取最小值 可行性 : 是否可行

    2023年04月08日
    浏览(45)
  • 【算法 - 动态规划】原来写出动态规划如此简单!

    从本篇开始,我们就正式开始进入 动态规划 系列文章的学习。 本文先来练习两道通过 建立缓存表 优化解题过程的题目,对如何将 递归函数 修改成 动态规划 的流程有个基本的熟悉。 用最简单的想法完成题目要求的 递归 函数; 定义明确 递归函数 的功能!!! 分析是否存

    2024年02月21日
    浏览(44)
  • 60题学会动态规划系列:动态规划算法第三讲

    简单多状态问题 文章目录 一.按摩师 二.打家劫舍系列 三.删除并获得点数 四.粉刷房子 力扣链接:力扣 一个有名的按摩师会收到源源不断的预约请求,每个预约都可以选择接或不接。在每次预约服务之间要有休息时间,因此她不能接受相邻的预约。给定一个预约请求序列,

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

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

    2024年01月16日
    浏览(45)
  • 60题学会动态规划系列:动态规划算法第二讲

    都是路径问题~ 文章目录 1.不同路径 2.不同路径II 3.礼物的最大价值 4.下降路径最小和 5.最小路径和 力扣链接:力扣 一个机器人位于一个  m x n   网格的左上角 (起始点在下图中标记为 “Start” )。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角(在

    2024年02月07日
    浏览(59)
  • 60题学会动态规划系列:动态规划算法第四讲

    买卖股票相关的动态规划题目 文章目录 1. 买卖股票的最佳时机含冷冻期 2. 买卖股票的最佳时期含⼿续费 3. 买卖股票的最佳时机III 4. 买卖股票的最佳时机IV 力扣链接:力扣 给定一个整数数组 prices ,其中第    prices[i]  表示第  i  天的股票价格 。​ 设计一个算法计算出最

    2024年02月13日
    浏览(34)
  • 60题学会动态规划系列:动态规划算法第五讲

    子数组系列题目 文章目录 1.最大子数组和 2.环形子数组的最大和 3.乘积最大数组 4.乘积为正数的最长子数组长度 5.等差数列划分 6.最长湍流子数组 7.单词拆分 8.环绕字符串中唯一的子字符串 力扣链接:力扣 给你一个整数数组  nums  ,请你找出一个具有最大和的连续子数组(

    2024年02月15日
    浏览(55)
  • 60题学会动态规划系列:动态规划算法第一讲

    坚持就是胜利 - -  文章目录 1.第N个泰波那切数 2.三步问题 3.使用最小花费爬楼梯 4.解码方法 力扣链接:力扣 泰波那契序列 Tn 定义如下:  T0 = 0, T1 = 1, T2 = 1, 且在 n = 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2 给你整数  n ,请返回第 n 个泰波那契数 Tn 的值。  首先我们分析一下

    2024年02月06日
    浏览(44)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包