动态规划之路径规划01

动态规划之路径规划01

前⾔：虽然⾃⼰做过⼏个动态规划的题⽬，看过题解后也能做出⼏个⼆维的路径问题，主要是对dfs进⾏优化。但是还是有点知其然不知其所以然的感觉，有两个⽉左右没做dp，现在让我写对⼀个⼆维路径dp都困难。所以开这个专题系统学习dp。感谢：宫⽔三叶

本笔记根据三叶⼤佬的刷题⽇记进⾏学习记录。

动态规划解决什么样的问题？答： 仅关⼼某个状态，⽽不关系状态如何转移过来（这句话很深奥，仔细体会）。常与dfs等搜索结合在⼀起，会保存⼦状态的解，且仅访问/遍历/执⾏⼀次，后续重复访问可直接利⽤此结果。

动态规划有相当多种类，其中最常见的就是路径问题和背包问题

⾸先从路径问题开始着⼿解决路径动态规划的⽅法：（以下是之前我⾃⼰总结的经验）1.确定状态转移⽅程。2.路径问题中遍历的⽅向。

做了专题训练后的总结：1.迭代⽅程

迭代⽅程根据边界判断的不同也会存在变化2.迭代⽅向

与遍历的⽅向和路径的⽅向选择有关3.初始条件

⼀般是最开始源点对应的dp值，赋值操作4.边界条件

边界时的迭代⽅程和⼀般迭代⽅程有⼀点差异

dp第⼀题试试⼿：

class Solution {public:

int uniquePaths(int m, int n) { int a[m][n]; a[0][0]=1;

//迭代⽅程：a[m][n]=a[m-1][n]+a[m][n-1]; for(int i=0;i0 && j>0){

a[i][j]=a[i-1][j]+a[i][j-1]; }else if(i>0){ a[i][j]=a[i-1][j]; }else if(j>0){ a[i][j]=a[i][j-1]; } } }

return a[m-1][n-1]; }};

本题迭代⽅程：a[m][n]=a[m-1][n]+a[m][n-1] 迭代⽅向：右和下 边界情况：上边缘，左边缘