工程建设项目网站,中小型网站建设如何,百度账号注册申请,怎么做素材网站序言
最近在学习python语言#xff0c;语言有通用性#xff0c;此文记录复习动态规划并练习python语言。
动态规划#xff08;Dynamic Programming#xff09;
动态规划是运筹学的一个分支#xff0c;是求解决策过程最优化的过程。20世纪50年代初#xff0c;美国数学家…序言
最近在学习python语言语言有通用性此文记录复习动态规划并练习python语言。
动态规划Dynamic Programming
动态规划是运筹学的一个分支是求解决策过程最优化的过程。20世纪50年代初美国数学家贝尔曼R.Bellman等人在研究多阶段决策过程的优化问题时提出了著名的最优化原理从而创立了动态规划。动态规划的应用极其广泛包括工程技术、经济、工业生产、军事以及自动化控制等领域并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。
基本思想将待求解问题分解成若干个子问题先求解子问题然后从这些子问题的解得到原问题的解。与分治法不同的是适合于用动态规划求解的问题经分解得到子问题往往不是互相独立的。
斐波那契数列Fibonacci sequence
斐波那契数列又称黄金分割数列因数学家莱昂纳多·斐波那契Leonardo Fibonacci以兔子繁殖为例子而引入故又称“兔子数列”其数值为1、1、2、3、5、8、13、21、34……在数学上这一数列以如下递推的方法定义F(0)1F(1)1, F(n)F(n - 1)F(n - 2)n ≥ 2n ∈ N*。
先以斐波那契数列为例了解动态规划。
def fibonacci(num):if num 0:return 1if num 1:return 1return fibonacci(num - 1) fibonacci(num - 2)if __name__ __main__:print(fibonacci(10))上述是以递归的方式实现的然而递归方式存在以下几个缺点
1递归调用占用空间大2递归太深容易发生栈溢出3可能存在大量重复计算
结果n-1项n-2项f(n)f(n-1)f(n-2)………f(5)f(4)f(3)f(4)f(3)f(2)f(3)f(2)f(1)f(2)f(1)f(0)
以上述表格为例可以看到在求下一个递归结果时计算了之前已经计算出来的结果存在重复计算项。
如果采用动态规划的方式那么可以节省计算采用数组暂存之前已经计算出来的结果。如下
def fibonacci_dp(num):# 定义一个数组暂存dp结果数组初始值为-1dp [-1] * (num 1)dp[0] 1dp[1] 1for i in range(2, num 1):dp[i] dp[i - 1] dp[i - 2]return dp[num]if __name__ __main__:print(fibonacci_dp(10))不同路径
上面的斐波那契数列是一维数组较为简单下面以二维数组为例。
题目描述
一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish” 。
问总共有多少条不同的路径 示例1: 输入m 3, n 7 输出28 示例2: 输入m 3, n 2 输出3 解释 从左上角开始总共有 3 条路径可以到达右下角。 1.向右 - 向下 - 向下 2.向下 - 向下 - 向右 3.向下 - 向右 - 向下 示例3: 输入m 7, n 3 输出28 示例4: 输入m 3, n 3 输出6 1 m, n 100 题目数据保证答案小于等于 2 * 10^9 python代码
class UniquePaths(object):def uniquePaths(self, m: int, n: int) - int::type m: int:type n: int:rtype: int# 初始化一个二维数组dp [[0] * n for _ in range(m)]for i in range(m):dp[i][0] 1for j in range(n):dp[0][j] 1for i in range(1, m):for j in range(1, n):dp[i][j] dp[i - 1][j] dp[i][j - 1]return dp[m - 1][n - 1]if __name__ __main__:demo UniquePaths()print(demo.uniquePaths(7, 3))最小路径和
题目描述
给定一个包含非负整数的 m x n 网格 grid 请找出一条从左上角到右下角的路径使得路径上的数字总和为最小。
说明一个机器人每次只能向下或者向右移动一步。 示例1 输入grid [[1,3,1],[1,5,1],[4,2,1]] 输出7 解释因为路径 1→3→1→1→1 的总和最小。 示例2 输入grid [[1,2,3],[4,5,6]] 输出12 提示 m grid.length n grid[i].length 1 m, n 200 0 grid[i][j] 100 python代码
class MinPathSum(object):def minPathSum(self, grid)::type grid: List[List[int]]:rtype: introw len(grid)column len(grid[0])# 定义dp[i][j]为到(i,j)处的最小路径和dp [[0] * column for _ in range(row)]dp[0][0] grid[0][0]# 第0行j列for j in range(1, column):dp[0][j] dp[0][j - 1] grid[0][j]# 第i行0列for i in range(1, row):dp[i][0] dp[i - 1][0] grid[i][0]# 非第0行或第0列for i in range(1, row):for j in range(1, column):dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) grid[i][j]return dp[row - 1][column - 1]if __name__ __main__:demo MinPathSum()grid [[1, 3, 1], [1, 5, 1], [4, 2, 1]]print(demo.minPathSum(grid))零钱兑换
题目描述
给你一个整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回 -1 。
你可以认为每种硬币的数量是无限的。 示例 1 输入coins [1, 2, 5], amount 11 输出3 解释11 5 5 1 示例 2 输入coins [2], amount 3 输出-1 示例 3 输入coins [1], amount 0 输出0 提示 1 coins.length 12 1 coins[i] 231 - 1 0 amount 104 python代码
class CoinChange(object):def coinChange(self, coins: list[int], amount: int) - int::type coins: List[int]:type amount: int:rtype: int# 状态转移方程dp(i) min(dp(i-Cj)) 1Cj为货币面值i0 忽略i0 dp[0] 0i1 dp[1] min(dp[1-1], dp[1-2], dp[1-5]) 1 1i2 dp[2] min(dp[2-1], dp[2-2], dp[2-5]) 1 1i3 dp[3] min(dp[3-1], dp[3-2], dp[3-5]) 1 2i4 dp[4] min(dp[4-1], dp[4-2], dp[4-5]) 1 2... ...dp [0] * (amount 1)dp[0] 0for i in range(1, amount 1):mini int(1e9)for coin in coins:if i coin:res dp[i - coin]if 0 res mini:mini resdp[i] mini 1 if mini int(1e9) else -1if amount 1:return 0return dp[amount]if __name__ __main__:demo CoinChange()coins [1, 2, 5]amount 11print(demo.coinChange(coins, amount))
