Dynamic Programming - Summary

https://stomachache007.wordpress.com/2017/11/06/%E4%B9%9D%E7%AB%A0%E7%AE%97%E6%B3%95%E9%AB%98%E7%BA%A7%E7%8F%AD%E7%AC%94%E8%AE%B05-%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92%EF%BC%88%E4%B8%8B%EF%BC%89/
https://medium.com/algorithms-and-leetcode/dp-c6797e0618a

满足下面三个条件之一，则极有可能使用动态规划 90% — 95%：

1. 求最大值，最小值
2. 判断是否可行
3. 统计方案个数

极不可能使用动态规划的情况：

1. 求出所有具体的方案而非方案的个数,要用DFS而不是DP(99%不用DP), 除了N皇后
2. 输入数据是一个集合而不是序列,输入数据是一个集合而非序列(70~80%不用DP)，除了背包问题
3. 暴力的算法已经是多项式级别, 本来时间复杂度就在O(n^{2})或者O(n^{3})的问题继续优化,因为不怎么能优化…(100%不用DP)• 动态规划擅长与优化指数级别复杂度(2^n,n!)到多项式级别复杂度(n²,n³), 不擅长优化n³到n²

动态规划的 4 点要素

1. 状态 State
   灵感，创造⼒，存储小规模问题的结果

• 最优解 / Maximum / Minimum
• Yes / No
• Count(*)

2. 方程 Function
状态之间的联系，怎么通过⼩的状态，来求得⼤的状态

3. 初始化 Initialization
最极限的小状态是什么，起点

4. 答案 Answer
最⼤的那个状态是什么，终点

总结

三种面试常见的动态规划类别及状态特点

• 坐标,单序列,双序列

两招独孤九剑

• 二维DP需要初始化第0行和第0列
• n个字符的字符串要开n+1个位置的数组

状态的六大问题:

1. 坐标型15%: jump game: 棋盘，格子 f[i]代表从起点走到i坐标
2. 序列型30%:f[i]代表前i个元素总和，i=0表示不取任何元素
3. 双序列型30%
4. 划分型10%
5. 背包型10%
6. 区间型5%

滚动数组优化

f[i] = max(f[i-1], f[i-2] + A[i]);

转换为

f[i%2] = max(f[(i-1)%2]和 f[(i-2)%2])




X. 坐标型
https://robinliu.gitbooks.io/algorithms/content/zuo_biao_xing.html
状态:
f[x] 从起点到坐标x的状态,
f[x][y]: 从起点到坐标`[x][y]的状态
方程: 研究走到x, y 这个点之前的一步
初始化: 起点
答案: 终点

64. Minimum Path Sum

function : f[x][y] = min(f[x-1][y], f[x][y-1]) + grid[x][y]

62. Unique Paths

63. Unique Paths II

function: f[x][y] = f[x-1][y] + f[x][y-1]

70. Climbing Stairs

function: f[i] = f[i-1] + f[i-2]

55. Jump Game

state: f[i]: 能否到第 i 个位置
function: f[i] = OR(f[j], j < i && j can reach i)

45. Jump Game II

state: f[i]: 跳到第 i 个位置最少要几步
function: f[i] = min {f[j] + 1, j < i && j can reach i}

300. Longest Increasing Subsequence

state: f[i]: 到 i 为止的最大上升序列
function: f[i] = max{f[j]+1} for j < i && nums[j] <= nums[i]

221. Maximal Square

state: f[i][j]: 表示以 i, j 作为正方形右下角的最大边长值
function: f[i][j] = min(f[i-1][j], f[i][j-1], f[i-1][j-1]) + 1 for matrix[i][j] == 1
f[i][j] = 0 for matrix[i][j] == 0

174. Dungeon Game

这一题是比较特殊的题目, 需要进行逆向考虑. int need = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
dp[i][j] = need <= 0 ? 1 : need;

91. Decode Ways

s[i - 1] == '0': ways[i + 1] = ways[i - 1];
s[i-1] != '0' && stoi(s.substr(i-1, 2)) <= 26: ways[i+1] = ways[i] + ways[i-1]
ways[i + 1] = ways[i]: all others

X. 单序列型
https://robinliu.gitbooks.io/algorithms/content/dan_xu_lie_xing.html
状态: f[i]: 表示前 i 个位置/数字/字符, 第 i 个
方程: f[i] = f[j]... j 是 i 之前的一个位置
初始化: f[0]
结果: f[n]
一般结果是f(n) 而不是 f(n-1) 因为对于 n 个字符, 包含前0个(空串), 前1个... 前 n 个.

139. Word Break

state: f[i]: 前 i 个字符能否被完美切分
function: f[i] = OR{f[j] && j + 1 ~ i is a word} j < i
initialize: f[0] = true;

132. Palindrome Partitioning II

state: f[i] 前 i 个字符组成的子串能被分割为最少多少个
function: f[i] = min {f[j] + 1}, j < i && j + 1 - i is palindrome
initial: f[i] = i
answer: f[n] -1

198. House Robber

state: f[i] 表示前 i 个房子中, 偷到的最大值
function: f[i] = max(f[i-1], f[i-2] + A[i])

213. House Robber II

House Robber I 的升级版, 不同的地方就是要考虑第一步的区别, 解两次House Robber I 就可以了了.

338. Counting Bits

举例观察就会发现 dp[2^i + j] = dp[2^(i-1) + j] + 1

276. Paint Fence

256. Paint House

265. Paint House II

120. Triangle

X. 双序列型
https://robinliu.gitbooks.io/algorithms/content/shuang_xu_lie_xing.html
状态: f[i][j] 表示第一个 sequence 的前 i 个, 与第二个 sequence 的前 j 个的关系
方程: f[i][j] 第 i 个和第 j 个的匹配关系
初始化: f[i][0] 和 f[0][j]
答案: f[m][n]

Longest Common Subsequence

state: f[i][j] 表示 前 i 个字符配上前 j 个字符的 LCS 的长度
function:
f[i][j] = max(f[i-1][j], f[i][j-1], f[i-1][j-1]+1) for A[i-1] == B[j-1]
f[i][j] = max(f[i-1][j], f[i][j-1]) for A[i-1] != B[j-1]

72. Edit Distance

115. Distinct Subsequences

state: f[i][j]: 表示 S 的前 i 个字符中选取 T 的前j 个字符有多少种方案
function:
f[i][j] = f[i-1][j] + f[i-1][j-1] for S[i-1] == T[j-1]
f[i][j] = f[i-1][j] for S[i-1] != T[j-1]

97. Interleaving String

state: f[i][j]: 表示 s1 的前 i 个字符和 s2 的前 j 个字符能否组成 s3 的前 i+j 个字符
fucntion: f[i][j] = (f[i-1][j] && s1[i-1] == s3[i+j-1]) || (f[i][j-1] && s2[j-1] == s3[i+j-1])

10. Regular Expression Matching

dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '.') , if (p[j-1] != '*')
dp[i][j] = (dp[i][j - 2] || dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.'), (p[j-1] == '*')
难点就是*的处理:
dp[i][j - 2]: 表示匹配 0 个, 即直接跳过模式串 a*.
dp[i-1][j] && (s[i-1] == p[j-2] || p[j-2] == '.'): 匹配当前串, 匹配成功需要前一步也是成功的.

44. Wildcard Matching

dp[i][j] = dp[i-1][j-1] && (s[i-1] == p[j-1] || p[j-1] == '?'), if (p[j - 1] != '*')
dp[i][j] = dp[i][j-1] || dp[i-1][j], if (p[j - 1] == '*')
难点同样在于*的匹配, 如何表示匹配0个或者多个.
dp[i][j-1] --> 表示忽略掉 *, 即要匹配0个.
dp[i-1][j] --> 表示使用*匹配当前的字符, 即忽略掉当前字符

X. 区间型
http://wiki.gyh.me/DP/%E5%8C%BA%E9%97%B4dp/

• 涉及到区间划分的问题可以归到此类
• 区间问题大多相似，都是枚举划分点，然后选择最优子结构

应按照j-i递增顺序递推,因为长区间的值依赖于短区间的值

https://robinliu.gitbooks.io/algorithms/content/qu_jian_lei.html

• 求一段区间的解的max/min/count
• 转移方程通过区间更新
• 从大到小的更新

共性就是最后求[0, n-1] 这样一个区间
逆向思维分析, 从大到小
逆向 ==> 类似分治法

https://robinliu.gitbooks.io/algorithms/content/bei_bao_lei.html

• 用值作为 DP 维度
• DP 的过程就是填写矩阵
• 可以滚动数组优化

http://blog.csdn.net/liuqiyao_01/article/details/8797438

     区间DP是一类在区间上进行动态规划的最优问题，一般是根据问题设出一个表示状态的dp，可以是二维的也可以是三维的，一般情况下为二维。然后将问题划分成两个子问题，也就是一段区间分成左右两个区间，然后将左右两个区间合并到整个区间，或者说局部最优解合并为全局最优解，然后得解。

    这类DP可以用常规的for循环来写，也可以用记忆化搜索来写，个人更倾向于记忆化搜索写法，因为这种写法相当易懂，要什么值你直接去记忆化搜索一下就ok了，随叫随到随用啊。

http://lixinzhang.github.io/qu-jian-xing-dp.html
区间形DP特征：

F[i][j]=F[i][k]+F[k+1][j]+CostFunction(i,j)

有n堆石子排成一列，每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子，一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序，能够使得总合并代价达到最小。

分析

设状态为F[i][j]$F[i][j]$，表示第i堆到第j堆石子合并之后的最小分值，那么其上一状态一定是由两个子堆合并而来，那么枚举中间分割位置k$k$为决策状态,因此状态转移方程：

F[i][j]=F[i][k]+F[k+1][j]+sum(i,j)$$F[i][j]=F[i][k]+F[k+1][j]+sum(i,j)$$

其中sum(i,j)$sum(i,j)$为两个自堆合并时，所产生的分值。

此类DP，先计算小区间，然后再通过小区间迭代得到大区间的值。

http://blog.leanote.com/post/mrazer/%E5%8C%BA%E9%97%B4DP%E6%80%BB%E7%BB%93

区间DP一般可以对于长度为1的时候直接赋值初始化，即：

for (int i=1;i<=n;++i) first（i）...//区间长度为1时初始化

2.注意顺序

方法一：对付区间DP最通用的方法就是直接上记忆化搜索，配合vis数组和inline也还是不错的（基本上也就不需要考虑转移顺序的问题了）。
方法二：按照区间长度进行DP，也比较通用，即：

    for (int len=2;len<=n;++len)
        for (int i=1;i<=n;++i)
        {
            int j=i+len-1;
            if(j>n)break;
            {solve（i,j）.../*处理*/}
        }

方法三：根据调查这种方法使用的人较少（尽管我经常用），原因就在于它适用范围较窄，但是另一方面它的常数的确略胜一筹：

    for (int i=n;i>=1;--i)
        for (int j=i+1;j<=n;++j)
        {solve(i,j).../*处理*/}

http://www.geeksforgeeks.org/count-arrays-adjacent-elements-one-divide-another/

Given two positive integer n and n. The task is to find the number of arrays of size n that can be formed such that :

1. Each element is in range [1, m]
2. All adjacent element are such that one of them divide the another i.e element Ai divides Ai + 1or Ai + 1 divides Ai + 2.

Input : n = 3, m = 3.
Output : 17
{1,1,1}, {1,1,2}, {1,1,3}, {1,2,1}, 
{1,2,2}, {1,3,1}, {1,3,3}, {2,1,1},
{2,1,2}, {2,1,3}, {2,2,1}, {2,2,2},
{3,1,1}, {3,1,2}, {3,1,3}, {3,3,1}, 
{3,3,3} are possible arrays.

Input : n = 1, m = 10.
Output : 10

We try to find number of possible values at each index of the array. First, at index 0 all values are possible from 1 to m. Now observe for each index, we can reach either to its multiple or its factor. So, precompute that and store it for all the elements. Hence for each position i, ending with integer x, we can go to next position i + 1, with the array ending in integer with multiple of x or factor of x. Also, multiple of x or factor of x must be less than m.
So, we define an 2D array dp[i][j], which is number of possible array (divisible adjacent element) of size i with j as its first index element.

1 <= i <= m, dp[1][m] = 1.
for 1 <= j <= m and 2 <= i <= n
  dp[i][j] = dp[i-1][j] + number of factor 
             of previous element less than m 
             + number of multiples of previous
             element less than m.

Time Complexity: O(N*M).

int numofArray(int n, int m)

{

    int dp[MAX][MAX];

    // For storing factors.

    vector<int> di[MAX];

    // For storing multiples.

    vector<int> mu[MAX];

    memset(dp, 0, sizeof dp);

    memset(di, 0, sizeof di);

    memset(mu, 0, sizeof mu);

    // calculating the factors and multiples

    // of elements [1...m].

    for (int i = 1; i <= m; i++)

    {

        for (int j = 2*i; j <= m; j += i)

        {

            di[j].push_back(i);

            mu[i].push_back(j);

        }

        di[i].push_back(i);

    }

    // Initalising for size 1 array for

    // each i <= m.

    for (int i = 1; i <= m; i++)

        dp[1][i] = 1;

    // Calculating the number of array possible

    // of size i and starting with j.

    for (int i = 2; i <= n; i++)

    {

        for (int j = 1; j <= m; j++)

        {

            dp[i][j] = 0;

            // For all previous possible values.

            // Adding number of factors.

            for (auto x:di[j])

                dp[i][j] += dp[i-1][x];

            // Adding number of multiple.

            for (auto x:mu[j])

                dp[i][j] += dp[i-1][x];

        }

    }

    // Calculating the total count of array

    // which start from [1...m].

    int ans = 0;

    for (int i = 1; i <= m; i++)

    {

        ans += dp[n][i];

        di[i].clear();

        mu[i].clear();

    }

    return ans;

}

http://www.geeksforgeeks.org/check-people-can-vote-two-machines/

There are n people and two identical voting machines. We are also given an array a[] of size n such that a[i] stores time required by i-th person to go to any machine, mark his vote and come back. At one time instant, only one person can be there on each of the machines. Given a value x, defining the maximum allowable time for which machines are operational, check whether all persons can cast their vote or not.

Let sum be the total time taken by all n people. If sum <=x, then answer will obviously be YES. Otherwise, we need to check whether the given array can be split in two parts such that sum of first part and sum of second part are both less than or equal to x. The problem is similar to the knapsack problem. Imagine two knapsacks each with capacity x. Now find, maximum people who can vote on any one machine i.e. find maximum subset sum for knapsack of capacity x. Let this sum be s1. Now if (sum-s1) <= x, then answer is YES else answer is NO.

bool canVote(int a[], int n, int x)

{

    // dp[i][j] stores maximum possible number

    // of people among arr[0..i-1] can vote

    // in j time.

    int dp[n+1][x+1];

    memset(dp, 0, sizeof(dp));

    // Find sum of all times

    int sum = 0;

    for (int i=0; i<=n; i++ )

        sum += a[i];

    // Fill dp[][] in bottom up manner (Similar

    // to knapsack).

    for (int i=1; i<=n; i++)

        for (int j=1; j<=x; j++)

            if (a[i] <= j)

                dp[i][j] = max(dp[i-1][j],

                        a[i] + dp[i-1][j-a[i]]);

            else

                dp[i][j] = dp[i-1][j];

    // If remaining people can go to other machine.

    return (sum - dp[n][x] <= x);

}

http://www.geeksforgeeks.org/minimum-operations-required-to-remove-an-array/

Given an array of N integers where N is even. There are two kinds of operations allowed on the array.

1. Increase the value of any element A[i] by 1.
2. If two adjacent elements in the array are consecutive prime number, delete both the element. That is, A[i] is a prime number and A[i+1] is the next prime number.

The task is to find the minimum number of operation required to remove all the element of the array.

To remove numbers, we must transform two numbers to two consecutive primes. How to compute the minimum cost of transforming two numbers a, b to two consecutive primes, where the cost is the number of incrementation of both numbers?
We use sieve to precompute prime numbers and then find the first prime p not greater than a and the first greater than p using array.

Once we have computed two nearest prime numbers, we use Dynamic Programming to solve the problem. Let dp[i][j] be the minimum cost of clearing the subarray A[i, j]. If there are two numbers in the array, the answer is easy to find. Now, for N > 2, try any element at position k > i as a pair for A[i], such that there are even number of elements from A[i, j] between A[i] and A[k]. For a fixed k, the minimum cost of clearing A[i, j], i.e dp[i][j], equals dp[i + 1][k – 1] + dp[k + 1][j] + (cost of transforming A[i] and A[k] into consecutive primes). We can compute the answer by iterating over all possible k.

int cost(int a, int b, int prev[], int nxt[])

{

    int sub = a + b;

    if (a <= b && prev[b-1] >= a)

        return nxt[b] + prev[b-1] - a - b;

    a = max(a, b);

    a = nxt[a];

    b = nxt[a + 1];

    return a + b - sub;

}

// Sieve to store next and previous prime

// to a number.

void sieve(int prev[], int nxt[])

{

    int pr[MAX] = { 0 };

    pr[1] = 1;

    for (int i = 2; i < MAX; i++)

    {

        if (pr[i])

            continue;

        for (int j = i*2; j < MAX; j += i)

            pr[j] = 1;

    }

    // Computing next prime each number.

    for (int i = MAX - 1; i; i--)

    {

        if (pr[i] == 0)

            nxt[i] = i;

        else

            nxt[i] = nxt[i+1];

    }

    // Computing previous prime each number.

    for (int i = 1; i < MAX; i++)

    {

        if (pr[i] == 0)

            prev[i] = i;

        else

            prev[i] = prev[i-1];

    }

}

// Return the minimum number of operation required.

int minOperation(int arr[], int nxt[], int prev[], int n)

{

    int dp[n + 5][n + 5] = { 0 };

    // For each index.

    for (int r = 0; r < n; r++)

    {

        // Each subarray.

        for (int l = r-1; l >= 0; l -= 2)

        {

            dp[l][r] = INT_MAX;

            for (int ad = l; ad < r; ad += 2)

                dp[l][r] = min(dp[l][r], dp[l][ad] +

                          dp[ad+1][r-1] +

                          cost(arr[ad], arr[r], prev, nxt));

        }

    }

    return dp[0][n - 1] + n/2;

}