动态规划（动态递推）

1. 将复杂问题拆分为多个子问题
2. 分治+最优子结构
3. 顺推：动态递推

DP顺推模板

function dp(){
    dp = [][] #二维情况
    
    for(int i = 0;i<M;i++){
        for(int j = 0;j<N;j++){
            dp[i][j] = _function(dp[i'][j']])
        }
    }
    retrun dp[M][N]
}

关键点：
动态规划和递推或者分支没哟根本上的区别（关键看有无最优的子结构）
拥有共性：找到重复子问题

不同路径2的PD方程
grid[i][j] = getPath(obstacleGrid, grid, m, n, i + 1, j) + getPath(obstacleGrid, grid, m, n, i, j + 1);