算法&OJ--其他--动态规划

发表于 | 分类于 | 阅读次数:
  • 动态规划小结
    • 常见题
    • 归类
  • （长路漫漫，未完待续ing）

动态规划的常见类型分为如下几种：

  • 矩阵型
  • 序列型
  • 双序列型
  • 划分型
  • 区间型
  • 背包型
  • 状态压缩型
  • 树型

其中，在技术面试中经常出现的是矩阵型，序列型和双序列型。划分型，区间型和背包型偶尔出现。状态压缩和树型基本不会出现（一般在算法竞赛中才会出现）。每种类型都有着自己的题目特点和状态的表示方法。
将所做过的动态规划问题按照这些类别进行归类，分析状态的表示方法和状态转移方程的构造方法在每种类型中的近似之处，会让你更快的学会动态规划。

总结与思考

  • DP问题注意
    • 递推式
    • 初值
    • 空间优化
  • 多练习，多思考–LeetCode 85，91，97，120，131，132，139，140，152

一、矩阵型

以矩阵型动态规划为例，一般题目会给你一个矩阵，告诉你有一个小人在上面走动，每次只能向右和向下走，然后问你比如有多少种方案从左上走到右下。这种类型状态表示的特点一般是使用坐标作为状态，如f[i][j]表示走到(i,j)这个位置的时候，一共有多少种方案。状态的转移则是考虑是从哪儿走到(i,j)这个坐标的。

例1.1 机器人走路径

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?

Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.

例1.2棋盘路径最小和

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.

二、序列型

序列型的动态规划，一般是告诉你一个序列。

例2.1 Best Time to Buy and Sell Stock 一

Say you have an array for which the i-th elements is the price of a given stock on day i. If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

例2.2 Best Time to Buy and Sell Stock 二

Say you have an array for which the i-th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

例2.3 Best Time to Buy and Sell Stock 三

Say you have an array for which the i-th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
Note: You may not engage in multiple transactions at the same time (ie, you must sell the sock before you buy again).

例2.5 连续子数组的最大和

在一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？
例如:{6,-3,-2,7,-15,1,2,2}的连续子向量的最大和为8(从第0个到第3个)。(子向量的长度至少是1)

1
2
3
4
5
6
7
8
9
10
int FindGreatestSumOfSubArray(vector<int> array) {
   if(array.empty()) return 0;
   int sum = array[0], tempsum = array[0]; //注意初始值 不能设为0 防止只有负数
   for(int i = 1; i < array.size(); i++) //从1开始 因为0的情况在初始化时完成了
   {
     tempsum = (tempsum < 0) ? array[i] : tempsum + array[i];
     sum = (tempsum > sum) ? tempsum : sum;
   }
     return sum;
 }

例2.6 数组其他元素的乘积

给定一个整数数组，编写一个函数来替换每个元素，使用除了该元素之外的所有元素的乘积来替换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void replaceWithProducts(int[] a, int n) {
    if(a==null || a.length==0 || a.length!=n) {
        return;
    }
    // 双向DP，双向累计不包含当前index的乘积
    int[] d1 = new int[n]; // 正向乘积累计
    int[] d2 = new int[n]; // 逆向乘积累计
    d1[0] = 1;
    d2[n-1] = 1;
    for(int i=1; i<n; i++) {
        d1[i] = a[i-1] * d1[i-1];
        d2[n-i-1] = a[n-i] * d2[n-i];
    }

    a[0] = d2[0];
    a[n-1] = d1[n-1];
    for(int i=1; i<n; i++) {
        a[i] = d1[i] * d2[i];
    }
}

三、双序列型

双序列的动态规划一般是告诉你两个字符串或者两个序列

例3.1 最长公共子串

对于两个字符串，请设计一个时间复杂度为O(m*n)的算法(这里的m和n为两串的长度)，求出两串的最长公共子串的长度。这里的最长公共子串的定义为两个序列U1,U2,..Un和V1,V2,…Vn，其中Ui + 1 == Ui+1,Vi + 1 == Vi+1，同时Ui == Vi。
给定两个字符串A和B，同时给定两串的长度n和m。

测试样例：”1AB2345CD”,9,”12345EF”,7

返回：4

例3.2 编辑距离

给定两个字符串S和T，求把S变成T所需要的最少操作次数。操作包括：在任意位置增加一个字符、减少一个字符以及修改任意一个字符(LeetCode 72)

换个角度思考问题，变为字符串对齐问题

  • S=”ABCF” T=”DBFG”
S A B C F -
T D B - F G
  • 打分
    • 对应位置相同不扣分
    • 两个特殊字符”-“不会对应
    • S位置”-“代表增加字符
    • T位置”-“代表删除字符
    • 使扣分最小

状态方程

  • dp[i][j]表示S的前i个位置和T的前j个位置对齐的最少得分
  • dp[i][j]=min(dp[i-1][j-1]+same(i,j), dp[i-1][j]+1, dp[i][j-1]+1)
    • dp[i-1][j-1]+same(i,j) 对应S第i个字符和T第j个字符对齐
    • dp[i-1][j]+1 对应S第i个字符和”-“对齐，即删掉S中第i个字符
    • dp[i][j-1]+1 对应T第j个字符和”-“对齐，即在S中增加该字符
  • 初值
    • dp[0][j]=j, dp[i][0]=i (i>=0, j>=0)
  • 时空复杂度
  • 空间优化–省掉一维
    • 对每个i，正向循环j(注意保存dp[i-1][j-1]，因为j-1已经是新值)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int minDistance(String word1, String word2) {
    char[] S = word1.toCharArray();
    char[] T = word2.toCharArray();

    int SLength = S.length;
    int TLength = T.length;
    int[][] dp = new int[SLength+1][TLength+1];

    for(int i=0; i<=SLength; i++) {
        for(int j=0; j<=TLength; j++) {
            if(i == 0) {
                dp[i][j] = j;
            } else if(j == 0) {
                dp[i][j] = i;
            } else {
                dp[i][j] = min(dp[i-1][j-1] + ((S[i-1]==T[j-1])?0:1),
                                min(dp[i][j-1] + 1, dp[i-1][j] + 1)
                              );
            }
        }
    }
    return dp[SLength][TLength];
}

四.区间型动态规划

例 4.1 LintCode-363.接雨水 系列一

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

image

  • 注意：此时竖边是有宽度的。

此题本质：某一bar的接水量=min(左边bar最大高度，右边bar最大高度)-bar高

  • 最直接的做法
    • 双数组，一个储存左边bar最大高度，一个储存右边bar最大高度
  • 有点绕的最优解
    • 两个记录最大高度的数组，自最大值出现后就不会被调用了(因为取得是min值)
    • 采用对撞型指针，每次让高度较小的指针移动即可
    • 该指针处接水量即为该方向最大值减去该处bar高
    • 循环直至两指针相遇于最高处
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public int trapRainWater(int[] heights) {
    // 双指针问题
    if(heights==null || heights.length<2) {
        return 0;
    }
    int water = 0;
    int left = 0;
    int right = heights.length - 1;
    int lMax = 0;
    int rMax = 0;
    while(left < right) {
        lMax = max(lMax, heights[left]);
        rMax = max(rMax, heights[right]);
        if(lMax < rMax) {
            water += lMax - heights[left];
            left++;
        } else {
            water += rMax - heights[right];
            right--;
        }
    }
    return water;
}
    
public int max(int a, int b) {
    return a>b?a:b;
}

五.others

5.1 爬台阶

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

5.2 矩形覆盖

我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

  • dp[0]=0 dp[1]=1 dp[2]=2
  • dp[i]=dp[i-1]+dp[i-2]
    • 此处可横着可竖着，所以递推式右边系两项
1
2
3
4
5
6
public int RectCover(int target) {
    if(target == 0) { return 0;}
    if(target == 1) { return 1;}
    if(target == 2) { return 2;}
    return RectCover(target-1) + RectCover(target-2);
}

无.似是而非

无.1 数组单调和

现定义数组单调和为所有元素i的f(i)值之和。这里的f(i)函数定义为元素i左边(不包括其自身)小于等于它的数字之和。请设计一个高效算法，计算数组的单调和。
给定一个数组A同时给定数组的大小n，请返回数组的单调和。保证数组大小小于等于500，同时保证单调和不会超过int范围。

测试样例：[1,3,5,2,4,6],6
返回：27