Skip to content

动态规划

动态规划

动态规划一般是当前的操作是通过之前的操作通过一些条件而得出来的; 这个条件就是状态转移方程；

解法

找出状态转移方程，根据组装一下数据，根据循环条件执行状态转移方程，求得结果进行返回;

例题

下面数字是leetcode题号

70

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？


第N阶,肯定是由N-1和N-2阶上来的，所以 第N阶的走法数必定是N-1+N-2的走法之和;
所以状态转移方程为
arr[N] = arr[N-1] + arr[N-2]

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 0:
            return 0
        if n == 1:
            return 1
        out = [0] * 46
        out[0], out[1] = 1, 1
        for i in range(2, n + 1):
            out[i] = out[i - 1] + out[i - 2]
        return out[n]

64

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

将走到第(i,j)的位置的结果置为out数组,
第out[i][j]的位置的值,肯定是min(out[i-1][j],out[i][j-1])加Arr[i][j]得到的，
所以状态转移方程为
out[i][j] = min(out[i-1][j],out[i][j-1])+Arr[i][j] 

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        # 先将数据置0
        out = [[0 for i in range(n)] for j in range(m)]
        # 第一步就是它自己
        out[0][0] = grid[0][0]
        # 第一排只能是从左往右
        for i in range(1, n):
            out[0][i] = out[0][i - 1] + grid[0][i]
        # 第一列只能是从上往下
        for i in range(1, m):
            out[i][0] = out[i - 1][0] + grid[i][0]
        # 执行状态转移
        for i in range(1, m):
            for j in range(1, n):
                out[i][j] = min(out[i - 1][j], out[i][j - 1]) + grid[i][j]
        return out[-1][-1]

62

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？

将走到第(i,j)的位置的结果置为ans数组,
第ans[i][j]的位置的值,肯定是ans[i-1][j]+ans[i][j-1]，可以从上面走来或者左边走来
所以状态转移方程为
ans[i][j] = ans[i-1][j]+ans[i][j-1]

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        # 置些空数据，用于改变
        ans = [[0 for i in range(n)] for j in range(m)]
        # 第一步就是它自己
        ans[0][0] = 1
        # 第一行其实都为1
        for i in range(1, n):
            ans[0][i] = ans[0][i - 1] + ans[0][i]
        # 第一列其实都为1
        for i in range(1, m):
            ans[i][0] = ans[i - 1][0] + ans[i][0]
        # 执行状态转移
        for i in range(1, m):
            for j in range(1, n):
                ans[i][j] = ans[i - 1][j] + ans[i][j - 1]
        return ans[-1][-1]

63

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish”）。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？
网格中的障碍物和空位置分别用 1 和 0 来表示

将走到第(i,j)的位置的结果置为ans数组,
分条件
    arr[i][j] = 0  第ans[i][j]的位置,肯定是ans[i-1][j]+ans[i][j-1]，可以从上面走来或者左边走来
    arr[i][j] = 1  第ans[i][j]的位置,走不通，置为0；

所以状态转移方程为
ans[i][j] = ans[i-1][j]+ans[i][j-1]

class Solution:
    def uniquePathsWithObstacles(self, grid: List[List[int]]) -> int:
        # 最开始有石头直接不同
        if grid[0][0] == 1:
            return 0
        m, n = len(grid), len(grid[0])
        # 组装数据
        out = [[0 for i in range(n)] for j in range(m)]
        # 第一个能走，有一种走法
        out[0][0] = 1
        # 第一行数据
        for i in range(1, n):
            if grid[0][i] == 1:
                out[0][i] = 0
            else:
                out[0][i] = out[0][i - 1] + grid[0][i]
        # 第一列数据
        for i in range(1, m):
            if grid[i][0] == 1:
                grid[i][0] = 0
            else:
                out[i][0] = out[i - 1][0] + grid[i][0]
        # 状态转移
        for i in range(1, m):
            for j in range(1, n):
                if grid[i][j] == 1:
                    out[i][j] = 0
                else:
                    out[i][j] = out[i - 1][j] + out[i][j - 1]
        return out[-1][-1]