什么是动态规划？

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。
动态规划算法是一种高效的求解最优化问题的方法。
动态规划常常适用于有重叠子问题和最优子结构性质的问题，可以通过记忆化存储子问题的解，避免重复计算，提高效率。

动态规划的核心思想是拆分子问题，记住过往，减少重复计算。

动态规划一般需要找到一个递推关系式，根据已知的边界条件和子问题的解，推导出原问题的解。

动态规划的应用

动态规划在实际中的应用极其广泛，包括工程技术、经济、工业生产、军事以及自动化控制等领域，并在背包问题、生产经营问题、资金管理问题、资源分配问题、最短路径问题和复杂系统可靠性问题等中取得了显著的效果。

如何求解动态规划？

一般来说，求解动态规划问题的思路步骤如下：

• 分析问题，确定是否具有最优子结构和重叠子问题的性质，即是否可以用动态规划来求解。
• 定义状态，即用一个或多个变量来描述问题的子问题。
• 找出状态转移方程，即用递推关系式来表示不同状态之间的联系。
• 确定边界条件，即初始状态和终止状态的值。
• 选择合适的存储结构，如数组、哈希表等，来保存子问题的解，并按照一定的顺序进行计算和填表。
• 根据存储结构中的结果，得出原问题的解，有时还需要进行回溯或者路径记录。

用刷题感受一下

初级

斐波那契数列

题目描述

第一二项为1，后面每项等于前两项和，求第n项

解题思路

每一项为前两项和，则dp[i]=dp[i-1]+dp[i-2],边界条件为dp[0]=1,dp[1]=1

Python

def fib(n):
    dp=[0]*n
    dp[0],dp[1]=1,1
    for i in range(2,n):
        dp[i]=dp[i-1]+dp[i-2]
    return dp[n-1]

print(fib(50))

爬楼梯

题目描述

爬楼梯：给定一个整数 n ，表示楼梯的阶数，每次可以爬 1 或 2 阶，求有多少种不同的方法可以爬到楼顶。

解题思路

这个问题可以用动态规划来求解，具体方法是定义一个数组 d ，其中 d [i] 表示爬到第 i 阶楼梯的方法数，那么 d [i] = d [i-1] + d [i-2] ，即爬到第 i 阶可以从第 i-1 阶爬 1 阶或者从第 i-2 阶爬 2 阶得到。

边界条件是 d [0] = 1 ，d 1 = 1

Python

def climbStairs( n: int) -> int:
        # 初始化数组
        d = [0] * (n + 1)
        # 边界条件
        d[0] = 1
        d[1] = 1
        # 状态转移方程
        for i in range(2, n + 1):
            d[i] = d[i - 1] + d[i - 2]
        # 返回结果
        return d[n]

print(climbStairs(6))
print(climbStairs(7))

最长上升子序列

题目描述

给定一个无序的整数数组，找到其中最长上升子序列的长度。

解题思路

这个问题也可以用动态规划来求解，具体方法是定义一个数组 dp ，其中 dp [i] 表示以 nums [i] 结尾的最长上升子序列的长度，那么 dp [i] = max (dp [j]) + 1 ，其中 j < i 且 nums [j] < nums [i] ，即在所有小于 i 的下标 j 中找到一个使得 nums [j] < nums [i] 的最大 dp 值，并加上自身长度 1 。

边界条件是 dp 数组全初始化为 1 。

Python

def lengthOfLIS(nums:list) -> int:
        # 初始化数组
        dp = [1] * len(nums)
        # 状态转移方程
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j]+1)
        # 返回结果
        return max(dp)

l=[1,2,3,4,6,5,8,7,8]
print(lengthOfLIS(l))

不同路径

题目描述

给定一个 m x n 的网格，从左上角开始，每次只能向右或者向下移动一步，到达右下角有多少种不同的路径。

解题思路

这个问题可以用动态规划来求解，具体方法是定义一个二维数组 dp ，其中 dp [i] [j] 表示从左上角到达 (i, j) 位置的不同路径数，那么 dp [i] [j] = dp [i-1] [j] + dp [i] [j-1] ，即到达 (i, j) 位置可以从上方或者左方移动一步得到。

边界条件是第一行和第一列都只有一种路径，即 dp [0] [] = 1 和 dp [] [0] = 1

Python

def uniquePaths(m: int, n: int) -> int:
        # 初始化二维数组
        dp = [[0 for _ in range(n)] for _ in range(m)]
        # 边界条件
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1
        # 状态转移方程
        for 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]

print(uniquePaths(2,2))
print(uniquePaths(3,20))

最小路径和

题目描述

最小路径和：给定一个 m x n 的网格，其中每个格子填写了非负整数，从左上角开始，每次只能向右或者向下移动一步，找到一条到达右下角的路径，使得路径上经过的数字之和最小。

解题思路

这个问题也可以用动态规划来求解，具体方法是定义一个二维数组 dp ，其中 dp [i] [j] 表示从左上角到达 (i, j) 位置的最小路径和，那么 dp [i] [j] = min (dp [i-1][j],dp[i][j-1]) + grid[i][j], 即到达 (i,j) 位置可以从上方或者左方移动一步得到，并加上当前格子的数字。

边界条件是第一行和第一列需要累加前面的数字之和。

Python

def minPathSum(grid) -> int:
        # 初始化二维数组
        m = len(grid)
        n = len(grid[0])
        dp = [[0 for _ in range(n)] for _ in range(m)]
        # 边界条件
        dp[0][0]=grid[0][0]
        for i in range(1,m):
            dp[i][0]=dp[i-1][0]+grid[i][0]
        for j in range(1,n):
            dp[0][j]=dp[0][j-1]+grid[0][j]
        # 状态转移方程
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]
        # 返回结果
        return dp[m-1][n-1]

l=[
     [1,2,3,4,5,6,7],
     [1,2,3,4,5,6,7],
     [1,2,3,4,5,6,7],
     [1,2,3,4,5,6,7],
     [1,2,3,4,5,6,7],
]
print(minPathSum(l))

最长公共子序列

题目描述

最长公共子序列：给定两个字符串 text1 和 text2 ，返回这两个字符串的最长公共子序列（LCS）的长度。一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，“ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。如果不存在公共子序列，返回 0 。

解题思路

这个问题可以用动态规划来求解，具体方法是定义一个二维数组 dp ，其中 dp [i] [j] 表示 text1[0:i] 和 text2[0:j] 的最长公共子序列长度，那么 dp [i] [j] 有以下两种情况：
如果 text1[i-1] == text2[j-1] ，则 dp [i] [j] = dp [i-1][j-1]+1 ，即在前面最长公共子序列基础上加上当前相同字符。
如果 text1[i-1] != text2[j-1] ，则 dp [i][j]=max(dp[i-1][j],dp[i][j-1]) ，即取前面两种可能中较大者。

边界条件是第一行和第一列都为 0 ，因为空串与任何串没有公共子序列。

持续更新中，遗忘请戳戳~~~

Python

斐波那契数列

题目描述

解题思路

C++

Python

斐波那契数列

题目描述

解题思路

C++

Python

斐波那契数列

题目描述

解题思路

C++

Python

斐波那契数列

题目描述

解题思路

C++

Python

动态规划的优缺点

动态规划有以下一些优缺点：

优点：

• 动态规划可以有效地解决一些具有重叠子问题和最优子结构的问题，避免了重复计算，提高了效率。
• 动态规划可以将复杂的问题分解为相对简单的子问题，降低了问题的难度，便于理解和求解。
• 动态规划可以在求解最优值的同时，还能得到最优解的具体方案，方便进行分析和应用。

缺点：

• 动态规划需要存储大量的中间结果，可能会占用较多的空间。
• 动态规划需要找到合适的状态定义和状态转移方程，这可能不是很容易做到，需要一定的技巧和经验。
• 动态规划对于一些没有明显最优子结构或者重叠子问题的问题，并不适用，可能会得到错误或者非最优的结果。