mojinhui33
0%

算法（一）：动态规划

发表于 更新于 分类于

算法（二）：动态规划

动态

动态规划：利用历史记录，来避免我们的重复计算，而这些历史记录，我们的需要一些变量来进行保存，一般是用一维数组或者二维数组来保存

动态规划的三大步骤

  1. 定义数组元素的含义
  2. 找出数组元素之间的关系式
  3. 找出初始值

    不一定要定义数组，这仅仅是一种思想

例：dp[n] = dp[n - 1] + dp[n - 2]
需要知道定义这个dp[]用来干啥的，然后得到关系式（最好找到最优子结构），最后找到dp[2]和dp[1]的值，因为他们不能够再分了，这就是所谓的初始值

案例一、小青蛙跳台阶（可用递归）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int f(int n){
    if(n <= 1){
        return n;
    }
    //先创建一个数组来保存历史记录
    int[] dp = new int[n + 1];
    //给定初始值
    dp[0] = 0;
    dp[1] = 1;
    dp[2] = 2;
    //通过关系式来计算出 dp[n],从上往下慢慢计算
    for(int i = 3; i <= n; i++){
        dp[i] = dp[i - 1] + dp[i -2];
    }
    return dp[n];
}

虽然用的是DP，但是没必要用到数组，有点浪费空间

1
2
3
4
5
6
7
8
9
int first = 0;
int second = 1;
int end = 1;
for(int i = 1; i <= n; i++){
    end = first+second;
    first = second;
    second = end;
}
return end;

案例二、二维数组的DP
问题描述：一个机器人从一个m * n网格的左上角到右下角，机器人每次只能向下或向右移动，有多少条不同的路径？

leetcode的62号题:

三步解决：

步骤一、定义数组元素的含义
定义 dp[i][j]的含义为：当机器人从左上角走到（i，j）这个位置是，一共有dp[i][j]种途径。那么，对着 dp[m - 1][n - 1] 走下去，即为答案

步骤二、找出关系数组元素间的关系式
机器人就只会向下走或向右走，那么
一种为（i-1，j）
一种为（i，j-1）
因为都有可能，所以关系式为 dp[i][j] = dp[i - 1][j] + dp[i][j -1 ]

步骤三、找出初始值 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int uniquePaths(int m, int n){
    if(m <= 0 || n <= 0){
        return 0;
    }
    int[][] dp = new int[m][n];
    //初始化
    for(int i = 0; i < m; i++){
        dp[i][0] = 1;
    }
    for(int i = 0; i < n; i++){
        dp[0][i] = 1;
    //推导出 dp[m-1][n-1]
    for(int i = 1; i < m; i++){
        for(int j = 1; j < m; j++){
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    return dp[m-1][n-1];
}

O(n*m)的空间复杂度可以优化成O(min(n, m))的空间复杂度



案例三、二维数组的DP

和案例二差不多，找出一条路径，使得路径上的数字总和为最小

这次不是计算所有可能的路径，而是计算哪一个路径最小，所以关系式找出来为

dp[i][j] = min(dp[i-1][j] dp[i][j-1]) +arr[i][j];

再找出初始值，如果i或j有一个为0，那么就不能用关系式了，此时i-1或j-1为负数，需要赋予初始值

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
    public static int uniquePaths(int[][] arr){
        int m = arr.length;
        int n = arr[0].length;
        if(m <= 0 || n <= 0){
            return 0;
        }
        
        int[][] dp = new int[m][n];
        dp[0][0] = arr[0][0];
        for(int i = 1; i < m; i++){
            dp[i][0] = dp[0][i-1] + arr[0][i];
        }
        for(int i = 1; i < m; i++){
            for(int j = 1; j < n; j++){
                dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + arr[i][j];
            }
        }
        return dp[m-1][n-1];
}

优化

将O(n*m)空间复杂度优化成O(n)

案例二

dp[i][j]是一个二维矩阵，每个点的值都与上一个或左边一个值有关（除了最左边和顶边的值），矩阵是一行一行的赋值，那么，当我们填充到第三行的值时，是不需要第一行的值的，这部分用不到的值，没有必要保存

所以，只用一个一维的dp[]来保存一行的历史记录就可以，然后历史记录dp[]会不断的更新，优化之后，代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int uniquePaths(int m, int n){
    if(m <= 0 || n <= 0){
        return 0;
    }

    int[] dp = new int[n];
    //初始化
    for(int i = 0; i < n; i++){
        dp[i] = 1;
    }

    for(int i = 1; i < m; i++){
        dp[0] = 1;
        for(int j = 1; j < n; j++){
            dp[j] = dp[j-1] + dp[j];
        }
    }
    return dp[n-1];
}