做网站的技术路线,谷歌生成在线网站地图,金沙网站怎么做代理,中端网站建设公司目录 基础内容#xff1a;
动态规划#xff1a;
动态规划理解的问题引入#xff1a;
解析#xff1a;#xff08;暴力回溯#xff09;
代码示例#xff1a;
暴力搜索#xff1a;
Dfs代码示例#xff1a;#xff08;搜索#xff09;
暴力递归产生的递归树
动态规划
动态规划理解的问题引入
解析暴力回溯
代码示例
暴力搜索
Dfs代码示例搜索
暴力递归产生的递归树
记忆化搜索
代码示例
动态规划
代码示例动态规划从最小子问题开始
执行过程动态规划
解析动态规划
空间优化
代码示例
解析 基础内容
什么是动态规划动态规划作为一种手段可以解决哪些问题动态规划的分类以及具体的分类可以解决的具体问题的分类。
动态规划
是一个重要的算法范式它将一个问题分解成一系列更小的子问题并通过存储子问题解避免重复计算从而大幅度提升时间效率。
动态规划理解的问题引入
通过爬楼梯的案例来引入这个问题给定一个共有n阶的楼梯你每步可以上1阶或者2阶请问有多少种方案可以爬到楼顶。
解析暴力回溯 本题目的目标是求解方案数量我们可以考虑通过回溯来穷举所有可能性。具体来说将爬楼梯想象为一个多轮选择的过程从地面出发每轮选择上一阶或者二阶每当达到楼梯顶部时就将方案数量加1当越过楼梯顶部就将其剪枝。
代码示例
# python代码示例
def backrack(choices,state,n,res) :if state n :res[0] 1 for choice in choices :if state choice n :continuebackrack(choices,statechoice,n,res)
def climbing_stairs_backrack(n) :choices [1,2]state 0res [0]backrack(choices,state,n,res)return res[0]
n int(input())
print(climbing_stairs_backrack(n))
// c代码示例
void backrack(vectorint choices, int state, int n, vectorint res)
{if (state n ){res[0] ;}for (auto choice : choices){if (state choice n){continue ;}backrack(choices, state choice, n, res)}
}int climbingStairsBackrack(int n)
{ vectorint choices {1 , 2 } ;int state 0 ;vectorint res [0] ;backrack(choices, state, n, res) ;return res[0] ;
}
暴力搜索
回溯算法通常并不显式地对问题进行拆解而是将问题看作一系列决策步骤通过试探和剪枝搜索所有可能的解。
我们可以尝试从问题分解的角度分析这道题。设爬到第i阶共有dp[i]中方案那么dp[i]就是原问题其子问题包括
dp[i-1]dp[i-2]dp[1]dp[2]
由于每轮只能上1阶或者2阶因此当我们站在第i阶楼梯上时上一轮只可能站在第i-1或者i-2台阶上。换句话说我们只能从第i-1阶或者第i-2阶迈向第i阶。
由此便可以得出一个重要的推论爬到第i-1阶的方案加上爬到第i-2阶的方案数就等于爬到第i阶的方案数。公式如下
dp[i] dp[i-1] dp[i-2]
这就意味着爬楼问题中存在着递推的关系原问题可由子问题的解构建来得到解决 Dfs代码示例搜索
# python 代码示例
def dfs(i : int) - int :if i 1 or i 2 :return icount dfs(i - 1) dfs(i - 2)return count
def climbing_stairs_dfs(n : int) - int :retunr dfs(n)// c 代码示例
int dfs(int i)
{if (i 1 || i 2){return i ;}int count dfs(i - 1) dfs(i - 2);return count ;
}
int climbingStairsDFS(int n)
{retunr dfs(n) ;
}
暴力递归产生的递归树 解决上述递归树中的重复问题采用记忆化搜索的方式可以把大量重复构建的相同子树进行去掉从而达到提高计算效率。重叠子问题
记忆化搜索
将所有重叠的子问题只进行一遍计算需要声明一个数组nem来记录每个子问题的解并在搜索过程中将重叠子问题剪枝。
当首次计算dp[i]时将其记录在nem[i]便于后续的使用当再次计算dp[i]时直接在nem[i]中进行获取结果避免重复子问题的计算。
代码示例
# python 代码示例
def dfs(i : int, mem : list[int]) - int :if i 1 or i 2 :return iif mem[i] ! -1 :return mem[i]count dfs(i - 1, mem) dfs(i - 2, mem)# 记录dfs(i)mem[i] countreturn count
def climbing_stairs_dfs_mem(n : int) - int :mem [-1] * (n 1)return dfs(n, mem)
// c 代码示例
int dfs(int i, vectorint mem)
{if (i 1 || i 2){return i ;}if (mem ! -1){return mem[i] ;}int count dfs(i - 1, mem) dfs(i - 2, mem) ;mem[i] count ;return count ;
}
int climbingStairsDFSMem(int n)
{vectorint mem(n 1, -1) ;return dfs(n, mem) ;
}
经过记忆化处理后所有重叠的子问题都只计算一次时间复杂度优化到了O(n) 动态规划
记忆化搜索是一种”从顶至低”的方法我们从原问题根节点开始递归地将较大子问题分解成较小子问题直至解已知的最小子问题叶节点。之后通过回溯逐层收集子问题的解构建出原问题的解。
与之相反动态规划是一种“从底至顶”方法从最小子问题的解开始迭代地构建更大子问题的解直至得到原问题的解。
由于动态规划不包含回溯过程因此只需要使用循环迭代实现无须使用递归。
代码示例动态规划从最小子问题开始
# python 代码示例
def clibing_stairs_dp(n) :if n 1 or n 2 :return ndp [0] * (n 1)dp[1], dp[2] 1, 2for i in range(3,n 1) :dp[i] dp[i-1] dp[i- 2]return dp[n]
// c 代码示例int climbingStairsDP(int n)
{if (n 1 || n 2){retunr n ;}vectorint dp(n 1, -1) ;dp[1] 1 ; dp[2] 2 ;for (int i 3 ; i n ; i){dp[i] dp[i - 1] dp[i- 2] ;}return dp[n] ;
}
执行过程动态规划 解析动态规划
相似于回溯算法动态规划也使用“状态”概念来表示问题求解的特定阶段每个状态都对应一个子问题以及相应的局部最优解。例爬楼梯问题的状态定义为当前所在楼梯的阶数i
根据以上内容我们可以总结为动态术语的常用术语
将数组dp称为{dp表}dp[i]表示状态i对应子问题的解将最小子问题对应的状态第一阶和第二阶楼梯称为初始状态将递推公式dp[i] dp[i-1] dp[i-2]称为状态方程
空间优化
dp[i] 只跟 dp[i-1] 和 dp[i-2] 有关
无须使用一个数组来存储所有子问题的解只需要两个变量滚动前进即可。
代码示例
# python 代码示例
def clibing_stairs_dp_comp(n) :if n 1 or n 2 :return na, b 1, 2for _ in range(3, n 1) :a, b b , a breturn b
// c 代码示例
int climbingStairsComp(int n)
{if (n 1 || n 2){return n ;}int a 1 , b 2 ;for (int i 3 ; i n ; i){int temp b ;b a b ;a temp ;}return b ;
}
解析
省去了数组dp所占用的空间空间复杂度由O(n)降为O(1)
在动态规划问题中当前状态仅与前面有限个状态有关这时我们可以只保留必要的状态通过“降维”来节省内存空间。这种空间优化技巧被称为“滚动变量”或“滚动数组”。 文章转载自： http://www.morning.rqqmd.cn.gov.cn.rqqmd.cn http://www.morning.nkyqh.cn.gov.cn.nkyqh.cn http://www.morning.jpwmk.cn.gov.cn.jpwmk.cn http://www.morning.gkgr.cn.gov.cn.gkgr.cn http://www.morning.pslzp.cn.gov.cn.pslzp.cn http://www.morning.glpxx.cn.gov.cn.glpxx.cn http://www.morning.zdqsc.cn.gov.cn.zdqsc.cn http://www.morning.ngcth.cn.gov.cn.ngcth.cn http://www.morning.swzpx.cn.gov.cn.swzpx.cn http://www.morning.skkmz.cn.gov.cn.skkmz.cn http://www.morning.cwlxs.cn.gov.cn.cwlxs.cn http://www.morning.zmtrk.cn.gov.cn.zmtrk.cn http://www.morning.rfkyb.cn.gov.cn.rfkyb.cn http://www.morning.lxqyf.cn.gov.cn.lxqyf.cn http://www.morning.dxpqd.cn.gov.cn.dxpqd.cn http://www.morning.zwgrf.cn.gov.cn.zwgrf.cn http://www.morning.dmwck.cn.gov.cn.dmwck.cn http://www.morning.llllcc.com.gov.cn.llllcc.com http://www.morning.kmprl.cn.gov.cn.kmprl.cn http://www.morning.xsgxp.cn.gov.cn.xsgxp.cn http://www.morning.qtxwb.cn.gov.cn.qtxwb.cn http://www.morning.prgyd.cn.gov.cn.prgyd.cn http://www.morning.txtgy.cn.gov.cn.txtgy.cn http://www.morning.hrtwt.cn.gov.cn.hrtwt.cn http://www.morning.jbnss.cn.gov.cn.jbnss.cn http://www.morning.tgtwy.cn.gov.cn.tgtwy.cn http://www.morning.mzskr.cn.gov.cn.mzskr.cn http://www.morning.fglyb.cn.gov.cn.fglyb.cn http://www.morning.rhfh.cn.gov.cn.rhfh.cn http://www.morning.mfxcg.cn.gov.cn.mfxcg.cn http://www.morning.jtmrx.cn.gov.cn.jtmrx.cn http://www.morning.gwxwl.cn.gov.cn.gwxwl.cn http://www.morning.tsycr.cn.gov.cn.tsycr.cn http://www.morning.qjsxf.cn.gov.cn.qjsxf.cn http://www.morning.stflb.cn.gov.cn.stflb.cn http://www.morning.jydky.cn.gov.cn.jydky.cn http://www.morning.mlzyx.cn.gov.cn.mlzyx.cn http://www.morning.bplqh.cn.gov.cn.bplqh.cn http://www.morning.zmyzt.cn.gov.cn.zmyzt.cn http://www.morning.nqnqz.cn.gov.cn.nqnqz.cn http://www.morning.lngyd.cn.gov.cn.lngyd.cn http://www.morning.xxiobql.cn.gov.cn.xxiobql.cn http://www.morning.btwrj.cn.gov.cn.btwrj.cn http://www.morning.pjwrl.cn.gov.cn.pjwrl.cn http://www.morning.wgzzj.cn.gov.cn.wgzzj.cn http://www.morning.crsqs.cn.gov.cn.crsqs.cn http://www.morning.shuangxizhongxin.cn.gov.cn.shuangxizhongxin.cn http://www.morning.qrpx.cn.gov.cn.qrpx.cn http://www.morning.jgttx.cn.gov.cn.jgttx.cn http://www.morning.ywndg.cn.gov.cn.ywndg.cn http://www.morning.stsnf.cn.gov.cn.stsnf.cn http://www.morning.rjznm.cn.gov.cn.rjznm.cn http://www.morning.ndynz.cn.gov.cn.ndynz.cn http://www.morning.rqgjr.cn.gov.cn.rqgjr.cn http://www.morning.qdzqf.cn.gov.cn.qdzqf.cn http://www.morning.rrgm.cn.gov.cn.rrgm.cn http://www.morning.dighk.com.gov.cn.dighk.com http://www.morning.wnbqy.cn.gov.cn.wnbqy.cn http://www.morning.xtlty.cn.gov.cn.xtlty.cn http://www.morning.ksggr.cn.gov.cn.ksggr.cn http://www.morning.ktblf.cn.gov.cn.ktblf.cn http://www.morning.xkwrb.cn.gov.cn.xkwrb.cn http://www.morning.kgslc.cn.gov.cn.kgslc.cn http://www.morning.myxps.cn.gov.cn.myxps.cn http://www.morning.mjxgs.cn.gov.cn.mjxgs.cn http://www.morning.zxhhy.cn.gov.cn.zxhhy.cn http://www.morning.khtyz.cn.gov.cn.khtyz.cn http://www.morning.rdkqt.cn.gov.cn.rdkqt.cn http://www.morning.dbtdy.cn.gov.cn.dbtdy.cn http://www.morning.rwmq.cn.gov.cn.rwmq.cn http://www.morning.banzou2034.cn.gov.cn.banzou2034.cn http://www.morning.lhytw.cn.gov.cn.lhytw.cn http://www.morning.mxnrl.cn.gov.cn.mxnrl.cn http://www.morning.gfhng.cn.gov.cn.gfhng.cn http://www.morning.hzryl.cn.gov.cn.hzryl.cn http://www.morning.qyhcg.cn.gov.cn.qyhcg.cn http://www.morning.yqgbw.cn.gov.cn.yqgbw.cn http://www.morning.khntd.cn.gov.cn.khntd.cn http://www.morning.ndrzq.cn.gov.cn.ndrzq.cn http://www.morning.ghccq.cn.gov.cn.ghccq.cn
