刷着LeetCode遇到了一道算路径数的题目，需要用DP来解决，然而并不会DP。于是，乘此机会开始学习DP。

前言

学习一个知识之前，要了解这个知识适用的范围和定义。

dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.

一种 Divide and Conquer 的模型，把一个大问题拆分成子问题，通过解决子问题进而解决大问题。(个人愚见)

接下来从 LeetCode 中的问题入手理解 DP。

Question

A robot is located at the top-left corner of a m x n grid (marked ‘Start’ in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below).

How many possible unique paths are there?

Unique Paths

Above is a 3 x 7 grid. How many possible unique paths are there?

Note: m and n will be at most 100.

Analysis

这道问题有两种解决方法，一种是数学，一种是DP，在此主要研究DP。

我们分析下，这个路径数是有规律的。

每一个小格的路径数是该小格上面和左边小格路径数之和。

换言之， 

1
paths[i,j] = paths[i-1,j] + paths[i,j-1]

其中，i和j分别为行和列，paths为二维数组存储 i x j 方格中每一格的路径数。

再仔细观察，第一行和第一列都有且只有一种走法，所以第一行和第一列的所有方格路径数仅为1。

也就是说我们只需要维护这个二维数组，将整个路径数遍历出来存储在里面，然后取出 paths 中最后一行最后一列的数字即为题目所要求的答案。

接下来用 Java 写出整个思路。

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int uniquePaths(int m, int n) {
        int[][] paths = new int[m][n]; // 创建 m x n 的二维数组存储路径数
        for(int i=0;i<m;i++)
            paths[i][0] = 1; // 初始化第一行全为1
        for(int j=1;j<n;j++)
            paths[0][j] = 1; // 初始化第一列全为1 (第一行第一列已经写了1，所以少一次循环)
        
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                paths[i][j] = paths[i-1][j] + paths[i][j-1]; // 开始维护我们的二维数组
            }
        }
        return paths[m-1][n-1]; // 返回题目所要答案
    }
}

总结

我们从上面的题目可以简单的理解动态规划的应用，拆分子问题，解决子问题，从而解决大问题。

如果不使用动态规划来解决，那么求每一格都需要重新算他的子问题，这样子的算法就会成为时间消耗达到指数级别的算法。

我们只需要新建一个数组存放之前计算过的路径数，把他当作缓存一样存放在数组中。

我们计算下一个格子的时候只需要做一次计算，而不需要重复计算子问题，减少时间消耗。

通俗来讲，这种方法叫做花费空间来节省时间，是一个很好用的技巧，但不是动态规划的本质，也不是动态规划的核心。

核心只有一个， Divide and Conquer —— 如何把大问题拆成好解决的小问题。

Reference

Dynamic programming

什么是动态规划？动态规划的意义是什么？

LeetCode : Unique Paths #62 - Github