概念

首先想到递归、分治。动态规划本质也一样。
共性：找到重复子问题
差异性：有最优子结构，中途可以淘汰次优解。

动态规划是分治+最优子结构。

例题

斐波那契数列

递归实现，时间复杂度是指数级。
最基础的写法为

int fib(int n){if (n <= 0){return 0;}else if(n==1){return 1;}else{return fib(n-1)+fib(n-2);}
}	

简化一点的表达为

int fib(int n){return n<=1 ? n : fib(n-1)+fib(n-2);
}

改变时间复杂度的方法：加一个缓存

int fib(int n, int[] memo){if(n<=1){return n;}if(memo[n]==0){memo[n]= fib(n-1) + fib(n-2);}return memo[n];
}

递归加记忆化搜索，即为自顶向下的方式。
从叶子节点开始的话就是自底向上。——动态规划模板

int fib(int n){if(n<=1){return n;}int[] fib = new int[n-1];fib[0]=0;fib[1]=1;for(int i=2;i<=n;i++){fib[i] = fib[i-1] + fib[i-2];}return fib[n];
}

路径计数

题目：只能向右和向下走，记有多少路径。
分治：

int countPaths(boolean[][]grid, int row , int col){if(!validSquare(grid,row,col)) return 0;if(isAtEnd(grid,row,col)) return 1;return countPaths(grid,row+1,col) + countPaths(grid,row,col+1);
}

DP:

if a[i,j] = ‘空地’{opt[i,j]=opt[i+1,j]+opt[i,j+1];
}else{opt[i,j]=0;	
}

class Solution {public int uniquePathsWithObstacles(int[][] obstacleGrid) {int m = obstacleGrid.length;int n = obstacleGrid[0].length;if(obstacleGrid[m-1][n-1]==1) return 0;int[] cur = new int[n]; // 一维数组表示cur[n-1] = 1; //初始化//最下一行for(int i = n-2; i >= 0 ; --i) {if(obstacleGrid[m-1][i] == 1){cur[i] = 0;}else{cur[i] = cur[i+1];}}// 动态规划递推for (int i = m-2; i >= 0; --i) {if (obstacleGrid[i][n-1] == 1) {cur[n-1] = 0; // 处理最右列的情况}for (int j = n-2; j >= 0; --j) {if (obstacleGrid[i][j] == 1) {cur[j] = 0;} else {cur[j] += cur[j + 1];}}}return cur[0];}
}