动态规划之路径规划01

前言：虽然自己做过几个动态规划的题目，看过题解后也能做出几个二维的路径问题，主要是对dfs进行优化。但是还是有点知其然不知其所以然的感觉，有两个月左右没做dp，现在让我写对一个二维路径dp都困难。所以开这个专题系统学习dp。

感谢：宫水三叶

本笔记根据三叶大佬的刷题日记进行学习记录。

动态规划解决什么样的问题？

答： 仅关心某个状态，而不关系状态如何转移过来（这句话很深奥，仔细体会）。常与dfs等搜索结合在一起，会保存子状态的解，且仅访问/遍历/执行一次，后续重复访问可直接利用此结果。

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

首先从路径问题开始着手

解决路径动态规划的方法：

1.确定状态转移方程。（以下是之前我自己总结的经验）

• 核心是找到状态转移方程，也就是迭代方程
• 迭代方程可能和dp无关
• 要注意满足dp的条件：迭代方程的右边必须是已经迭代（遍历赋值过dp）的元素，dp在二维数组中需要根据你遍历方向来确定dp数组的迭代方式。相同迭代方程的条件下，不同的遍历方向将会有不同的dp比较赋值语句。
• 对矩阵dp时的边界条件，有些节点无法直接带入状态转移方程，要么处理边界if，要么舍弃边界的dp值

2.路径问题中遍历的方向。

dp第一题试试手：

62. 不同路径

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]
   迭代方向：右和下
   边界情况：上边缘，左边缘