算法笔记（一）动态规划

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法笔记（一）动态规划，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2409字，纯文字阅读大概需要4分钟。

内容图文

许多大厂的面试都会考动态规划，为了能过算法题这关，把自己做的题的思路总结一下，方便日后查阅。

动态规划原理

简单点说，就是在计算过程中的某一步时，可以利用上一步计算得出的结果来进行决策。直接看个例子就懂了。

LeetCode 62题

链接: 62.不同路径.

这是LeetCode上一道中等难度的题，其实思路非常好理解。
首先一般动态规划的题分成三步：

• 定义数组
• 定义状态转移方程
• 给定初始值

定义数组

由于此题求解从左上角到右下角一共多少条路径。那么一般来讲问什么就设什么。
那么此题设从左上角走到位置（i， j）时，一共有 dp[i][j]种不同的路径。
对于一道动态规划的题，定义数组时要牢记数组所代表的含义。那么对于此题，即求解 dp[m][n]。

---

定义状态转移方程

所谓“状态转移”即我们要求解的dp[i][j]是通过另一个最相邻的状态计算而得知的，此状态一般是在前一时刻的状态，那么对于机器人已经在位置（i，j）的时刻k，我们要寻找k-1时刻机器人的位置。

根据题意，机器人只能往下走一步或者往右走一步。所以在k-1时刻，机器人的位置可以为 （i-1，j）或者（i，j-1）即

• 机器人在位置（i-1，j）右移一步到达（i，j）
• 机器人在位置（i，j-1）下移一步到达（i，j）

此时如果你牢记dp数组的含义的话，可以很快的想到

• dp[i][j] = dp[i-1][j] + dp[i][j-1]

上式即为状态转移方程，也时动态规划算法的核心思想：
对于此题，你不需要关注机器人走到位置[i-1][j]一共有多少种走法，只要知道对于[i-1][j]只有一种走法到达位置[i][j]。同理对于在位置[i][j-1]的机器人也只有一种走法到达位置[i][j]。

那么机器人到达位置[i][j]的走法自然为:到达位置[i-1][j]的走法dp[i-1][j]乘以[i-1][j]到达[i][j]的走法（1种） 再加上到达[i][j-1]的走法dp[i][j-1]乘以 从[i][j-1]到达[i][j]的走法（1种）

---

给定初始值

如果i或者j为1的话，上述关系式就失效了，因为i，j都是某个具体位置，i-1和j-1不能为零。

注意在编写代码中，数组的下标为从0开始，此处仅为了便于理解

故对于dp[1][2…n]和dp[2…m][1]我们需要人为的给出初始值。
此时回想dp数组的含义。对于dp[1][1…n]相当与机器人在第一行的各个位置，如下图这6个位置（不包括初始位置）。

这六个位置中想要到达任意一个位置只有一种走法：一直往右走。

注意，dp数组的含义是不同的走法次数，而不是走了多少次

同理另外一个方向也只有一种走法：一直往下走

定义初始值：

dp[1] [2….n] = 1;

dp[2…m] [1] = 1;

---

最后就是代码实现了：

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n] + [[1] + [0] * (n - 1) for _ in range(m - 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]

或者

import numpy as np
def uniquePaths(m: int, n: int) -> int:
    dp = np.ones([m, n])
    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]

内容总结

以上是互联网集市为您收集整理的算法笔记（一）动态规划全部内容，希望文章能够帮你解决算法笔记（一）动态规划所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---