解锁动态规划的奥秘：从零到精通的创新思维解析（3）

解锁动态规划的奥秘：从零到精通的创新思维解析（3）

前言：

小编在前几日书写了关于动态规划习题的博客（PS：其实这些都是我的存稿，我已经好久没写博客了截止到现在，确实摆烂），今天各位继续跟着小编的步伐，走进动态规划的世界，接下来我们将会·讲述一个比较新的动态规划问题：路径问题。

正文：

1.不同路径

1.1.题目来源

本题和之前的题目一样，都是来自于力扣，下面小编给上链接：62. 不同路径 - 力扣（LeetCode）

1.2.题目解析

和之前的规矩一样，小编先给各位分析一下题目到底想要传达给我们什么信息，其实本题也是很好理解的，这个题目就像我们小学做过的益智游戏一样，此时给定我们一个机器人，此时我们从左上角开始走，想要我们求解走到右下角的方法有几种，此时我们选择往右走，也可以选择往下走，只要走到右下角即可。这就是一个典型的路径问题，通过动态规划我们就可以轻易解决此类问题，下面小编进入本题的思路讲解部分。

1.3.思路讲解

对于动态规划的题目，我们首先需要先设置好一个dp表用于存放数据，此时根据题目分析我们可以知道此时我们需要设置一个二维的dp表，因为我们可以通过行走，也可以通过列走。设置完表后，此时我们就要五步走来解决动态规划的题目了。

1.状态表示

此时我们需要弄清楚此时的dp表是什么，对于线性的dp表示，我们通常可以是经