【算法】动态规划题目分析和解题步骤，例题：机器人从左上角只能向右向下到右下角有多少种不同的方式

第一次觉得动态规划题目这么清晰明了 

一. 动态规划题目特点：

1.计数类

1. 有多少种方式走到右下角
2. 有多少种方法选出k个数使得和是sum

2.求最大最小值问题

1. 从左上角到右下角路径的最大数字和
2. 最长上升子序列长度

3. 求存在性

1. 石子游戏，先手是否必胜
2. 能不能选出k个数使得和是sum

 

二. 动态规划的解题步骤：

1. 确定状态
   1. 最后一步：最优策略挪动的最后一步
   2. 子问题：比原问题规模小
2. 转移方程
3. 初始条件和边界情况
   1. 初始条件通常是转移方程计算不出来的所以需要手动定义
   2. 边界条件，不能越界
4. 计算顺序
   1. 大部分题目是转移方程的左边计算时，等式右边已经计算出来了的顺利
   2. 通常是从左到右、从上到下

例题：机器人从左上角，每一步只能向右向下，有多少种不同的方式到右下角

• 最后一步：机器人总要到达右下角，到达右下角的两种方式只能是向下向右，因此最后一步是向右或向下
• 子问题：如果有X种方式从左上角走到（m-2， n-1），有Y种方式从左上角走到（m-1， n-2），则机器人有X+Y种方式走到（m-1， n-1）,子问题有多少种方法走到（m-2, n-1）和（m-1， n-2）
• 状态：原问题里面有几个变量通常需要几维数组，这个问题种是二维数组。设f[i][j] 为机器人有多少种方式从到左上角走到（i, j）
• 转移方程：f[i][j] = f[i-1][j] + f[i][j-1]
• 初始条件：f[0][0] = 1
• 边界情况：第一行或第一列，每一步只能有一个方向过来，因此i = 0或j = 0， f[i][j] = 1
• 计算顺序：转移方程f[i][j] = f[i-1][j] + f[i][j-1]，左边计算时需要用到右边，因此需要先算出右边来，因此，从小到大去计算，i从0-m, j 从0-n;
• 时间复杂度：O(MN)
• 空间复杂度：O(MN)

public class Solution{
	public int uniquePaths(int m, int n) {
		int [][] f = new int[m][n];
		
		int i, j;
		for(i = 0; i < m; i++) { //行，从上到下
			for (j = 0; j < n; j++) { //列，从左到右
				if (i == 0 || j == 0) {
					f[i][j] = 1;
				}else {
					f[i][j] = f[i-1][j] + f[i][j-1];
				}
			}
		}		
		return f[m-1][n-1];
	}
}