动态规划：将多阶段问题转化为单阶段求解的优化决策方法

咱们平时总会遇到些难缠的麻烦事，这些可不是一蹴而就的，得慢慢来，得做决策和调整。这时候用动态规划超棒，能把复杂问题简化成几个小步骤。逐个击破，不仅能迅速找到答案，还能边干边积累经验。现在，我就给大家详细讲解一下动态规划的关键点，好让大家更深刻地体会到这方法的强大。

一、动态规划的基本概念

动态规划，就是先简化大难题成小难题解决，这些小难题之间有联系，一个难题的解可助解决下一个。跟分治法不同，分治法是把问题拆成无关的小问题，而动态规划更侧重于小难题间的联系。

老遇到这些让人心烦的重复小问题，这时候就体现动态规划牛了。干嘛每次都从零开始，记下来答案不就好了？这样一来，能省好多计算时间，效率也提高了。

二、动态规划的适用条件

不是所有困难问题都能单靠动态规划解决。一般来说，那些适合用动态规划解决的问题，得满足三个条件。第一是优化标准，意思是最优的解决方案是由各个子问题的最佳方案拼凑起来的。换句话说，如果每小部分的最优解都搞定了，那整体问题也就顺带最优了。

这事儿得分解成能叠加的小问题才行，解决时有些小麻烦得解决多遍。没了这个特性，动态规划就没什么厉害的，甚至可能不如别的算法。说到底，动态规划能搞定那些得分步骤做选择的复杂问题，最后这些选择还能决定结果。

三、动态规划的解决过程

用动态规划处理问题，得按几个步骤来。先得把问题拆成几个部分，要么按时间要么按空间，得好好整理好。要是这点搞不定，后面的解题过程就麻烦了。

咱们得先搞定状况和那些关键因素。每个步骤情况各异，得用不同情况描述。把这些状况搞透了，咱们才能专心解题。不明状况，做决定可就头疼了。

四、状态转移与决策制定

这玩儿的是动态规划的门道儿，得顺着上一期的状态和决定来弄这一期的状态。通常咱们是倒着来，先瞧瞧前后两期的状态咋变，再定策略转状态。

做选择前，先列出各种可能的方案，挑出看起来最靠谱的几个。得仔细点处理，因为每一步都可能影响到后面的决定和后果。

五、边界条件与复杂度分析

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
    	# 开数组 27 个位置的数组
        f = [float("inf")] * (amount+1) 
        # 初始条件：0元0种方法
        f[0] = 0
        n = len(coins)
        #f[1],f[2]....f[27]
        #每个数组空间装当前零钱最优的拼凑结果
        for i in range(1,amount+1):
        	#对每种零钱进行遍历
        	#转移方程f[X] = min{f[X-2]+1 , f[X-5]+1 , f[x-7]+1}
            for j in range(0,n):
                if(i>=coins[j]):
                    f[i] = min(f[i-coins[j]]+1,f[i])
        #如果凑不出目标数，返回-1
        if f[-1] == float("inf"):
            return -1
        #返回次数
        else:return f[-1]

做动态规划，关键是要找准那个边界，那可是状态变迁的终极点，搞准了才能继续计算。把边界条件说明白非常重要，这样才能确保计算是准确的。还得把每一步、每个状态还有怎么过渡的逻辑都搞懂，才能写出完整的转换方程。

关于时间成本和空间消耗，动态规划通常是时间上平方级别的，就是O(n^2)，空间上则是线性的，也就是O(n)。虽然比贪心算法慢点，但遇到那些难题，它在速度和准确度上可是超强滴。

咱们平时做决定，得慢慢来分步走，像规划个旅行或者排工时这样的。你有没有碰到过类似的难处？下面留言分享一下，顺便给个赞或转发，让更多的小伙伴看看动态规划的用处！

import numpy as np
def uniquePaths(m,n):   #m:行 ,n:列 5 4
	#如果用([0]*m)*n会涉及到拷贝问题
    f = np.zeros((m,n),dtype=np.int)
    for j in range(n):
        for i in range(m):
        	#边界为0的情况下均为1步
            if(i==0 or j==0):
                f[i][j] = 1
            #转移方程
            else:
                f[i][j] = f[i-1][j]+f[i][j-1]
    return f[i][j]
uniquePaths(5,4)

本文 融资融券杠杆炒股 原创，转载保留链接！网址：http://www.cdkaixi.cn/zmt/377.html