DP问题大集合之二

之前讲到过简单的DP问题参见此处，是由DFS引出来的，现在来看看正规的DP问题，DP集合之二。

72.Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)
You have the following 3 operations permitted on a word:
a) Insert a character
b) Delete a character
c) Replace a character

87.Given a string s1, we may represent it as a binary tree by partitioning it to two non-empty substrings recursively.
Below is one possible representation of s1 = "great":

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

To scramble the string, we may choose any non-leaf node and swap its two children.
For example, if we choose the node "gr" and swap its two children, it produces a scrambled string "rgeat".

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

We say that "rgeat" is a scrambled string of "great".
Similarly, if we continue to swap the children of nodes "eat" and "at", it produces a scrambled string "rgtae".

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

We say that "rgtae" is a scrambled string of "great".
Given two strings s1 and s2 of the same length, determine if s2 is a scrambled string of s1.

174.Dungeon Game
The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.
The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.
Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0’s) or contain magic orbs that increase the knight’s health (positive integers).
In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

都是hard难度…

[leetcode 72] Edit Distance

求使得两个字符串相等需要编辑的最小步数
其中编辑包括删除，增加，替换，均为1步
DP问题的通项公式：
用dp[i][j]表示使长度为i的字符串和长度为j的字符串相等需要编辑的最小步数
求解第一个字符串从0到i和第二个字符串从0到j需要编辑的最小步数（从后往前编辑），无非由以下几种情况得到：

1. 删除第一个字符串的第i个字符
2. 删除第二个字符串的第j个字符
3. 第i个字符和第j个字符相等，转到求解第一个字符串从0到i-1和第二个字符串从0到j-1需要编辑的最小步数
4. 第i个字符替换成第j个字符（或反之），然后转到求解第一个字符串从0到i-1和第二个字符串从0到j-1需要编辑的最小步数

这些情况中找出最小的情况即为dp[i][j]
那么可以写成如下的通项公式：

$$temp1=min(dp[i][j-1],dp[i-1][j])\\ temp2=dp[i-1][j-1] \,\,if\,\,s1[i]==s2[j]\,\,else\,\,dp[i-1][j-1]+1\\ dp[i][j]=min(temp1,temp2)$$

接下来要找通项公式的初始条件
即当i=0或者j=0的时候，值应该为多少，dp[0][k]=?
答案是显然的，当第一个字符串为空，第二个字符串长度为k，要使两个字符串相等，只需要对第一个字符串增加k步，或者是对第二个字符串删除k步，那么初始条件如下：

$$dp[i][0]=i\\ dp[0][j]=j$$

有了通项公式和初始条件，那么问题就解决了;
最后代码当然不能写成递归形式了，因为会有重复的情况，用for循环
代码如下：

public int minDistance(String word1, String word2) {
    int n=word1.length()+1;//此处是从0到n，即包括0，也包括n
    int m=word2.length()+1;
    int [][]dp=new int[n][m];
    int temp1,temp2;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(i==0)dp[i][j]=j;
            else if(j==0)dp[i][j]=i;
            else{
                temp1=dp[i-1][j]<dp[i][j-1]?dp[i-1][j]+1:dp[i][j-1]+1;//删除
                if(word1.charAt(i-1)==word2.charAt(j-1))temp2=dp[i-1][j-1];//相等
                else temp2=dp[i-1][j-1]+1;//替换
                dp[i][j]=Math.min(temp1,temp2);
            }
        }
    }
    return dp[n-1][m-1];
}

[leetcode 87] Scramble String

题意就是对字符串分割，每一次分割都可以分为两部分，直到不能再分割，组成一棵二叉树，其中二叉树的每个节点的左右子节点都可以交换，那么将其还原为字符串时，便可以产生新的字符串问，给定s2是否为s1这样的新字符串？显然dfs可解，不过超时，那么只能用DP解决了（当然还有剪枝的做法,可以参考leetcode中解法）
首先想到的时递归，如下：

/*
dfs
分割字符串，相当于比较前半部分和后半部分是否满足要求，或者比较后半部分，前半部分是否匹配（交换）
 */
public static boolean isScramble(String s1, String s2) {
    if(s1.equals(s2))return true;//如果相等，返回true
    if(s1.length()==1)return false;//如果不相等，且长度为1，返回false
    boolean result=false;
    for(int i=1;i<s1.length();i++){
        result=isScramble(s1.substring(0,i),s2.substring(0,i))&&isScramble(s1.substring(i),s2.substring(i));
        if(result==true)return true;
        result=isScramble(s1.substring(i),s2.substring(0,s2.length()-i))&&isScramble(s1.substring(0,i),s2.substring(s2.length()-i));
        if(result==true)return true;
    }
    return result;
}

leetcode上超时，dp解法参照http://blog.csdn.net/ljiabin/article/details/44537523
其中dp[i][j][len]，表示从s1的第i个字符开始长度为len的子串，和从s2的第j个字符开始长度为len的子串，是否互为scramble
其通项公式如下：

$$dp[i][j][1]=true \,\, \,\, if\,\,\,\,s1[i]==s2[j]\,\,\,else\,\,\,\,false\\ dp[i][j][len]=\sum_{k=1}^{len-1}(dp[i][j][k]\,\,and\,\,dp[i+k][j+k][len-k])\,\,or\\ \,\,(dp[i][j+len-k][k]\,\,and\,\,dp[i+k][j][len-k])$$

代码如下：

public static boolean isScramble2(String s1, String s2) {
    if(s1.length()!=s2.length())return false;
    if(s1.equals(s2))return true;
    boolean[][][]dp=new boolean[s1.length()][s2.length()][s1.length()+1];
    for(int i=0;i<s1.length();i++){
        for(int j=0;j<s2.length();j++){
            dp[i][j][1]=s1.charAt(i)==s2.charAt(j);
        }
    }
    for(int len=2;len<=s1.length();len++){
        for(int i=0;i<s1.length()-len+1;i++){
            for(int j=0;j<s2.length()-len+1;j++){
                for(int k=1;k<len;k++){
                    dp[i][j][len]|=(dp[i][j][k]&&dp[i+k][j+k][len-k])||(dp[i][j+len-k][k]&&dp[i+k][j][len-k]);
                }
            }
        }
    }
    return dp[0][0][s1.length()];
}

[leetcode 174] Dungeon Game

题目意思就是说，勇士从左上角出发，公主在右下角，勇士需要救出公主，每一步中的值代表勇士消耗/增加的能量，勇士走过每一步后必须保证剩余能量大于等于1，那么勇士从左上角出发最少需要带上多少能量才能救出公主？
dp我是不会做的，想了一会没想出来，就先用dfs做，每次记录走过当前步所需要的最小能量(minHealth)，以及当前路线的能量总和(currHealth)，当走完最后一步后返回minHealth就可以了，最后依次比较返回的结果，将最小的返回，代码如下：

public int calculateMinimumHP2(int[][] dungeon) {
    return dfs(0,0,dungeon,1,0);
}

private int dfs(int i, int j, int[][] dungeon, int minHealth, int currHealth) {
    if(i==dungeon.length-1&&j==dungeon[0].length-1){
        return currHealth+dungeon[i][j]+minHealth>0?minHealth:-(currHealth+dungeon[i][j])+1;
    }
    currHealth+=dungeon[i][j];
    minHealth=currHealth+minHealth>0?minHealth:-currHealth+1;
    int temp1=0,temp2=0;
    if(i<dungeon.length-1)temp1=dfs(i+1,j,dungeon,minHealth,currHealth);
    if(j<dungeon[0].length-1)temp2=dfs(i,j+1,dungeon,minHealth,currHealth);
    if(temp1!=0&&temp2!=0) return temp1>temp2?temp2:temp1;
    return temp1==0?temp2:temp1;
}

显然这道题必须用dp解决，上述代码leetcode提交结果为40/44,TLE ，看了看discuss的解答，我之前构建dp的时候是顺序的，但是顺序无法用dp解决，因为对于dp[i][j]，不能简单地取dp[i-1][j]和dp[i][j-1]中的最小值，因为currHealth也会影响，discuss中采用的是逆序，从右下到左上，这样就完全确定下来了，以下面这个例子为例：

-2,-3,3
-5,-10,1
10,30,-5

其中dp[i][j]表示的是从i，j点到右下角需要的最小能量.
对于右下角的-5，最小能量为6；对于上一行的1，我们只需要5就可以了；对于30而言，只需要1就可以了；对于-10而言，因为dungeon值小于0，那么我们至少需要使之大于等于0，再加上两条路径的最小值；也就是说对于任意点(i,j)，我们必须满足使该点得值大于等于0，然后在dp矩阵中找到dp[i-1][j],dp[i][j-1]中较小的一个就可以了，如下结果：

7,5,2
6,11,5
1,1,6

dp公式如下：

$$when\,\,i=m-1,j=n-1\,\,:\\ dp[i][j]=1 \,\,if\,\,dungeon[i][j]>0\,\,else\,\,1-dungeon[i][j]\\ when\,\,i=m-1\,\,:\\ dp[i][j]=dp[i][j+1]-dungeon[i][j]\,\, if\,\,dp[i][j+1]-dungeon[i][j]>0\,\,else\,\,1\\ when\,\,j=n-1\,\,:\\ dp[i][j]=dp[i+1][j]-dungeon[i][j]\,\, if\,\,dp[i+1][j]-dungeon[i][j]>0\,\,else\,\,1\\ else\,\,i,j\,\,:\,\,temp=min(dp[i+1][j],dp[i][j+1])\\ dp[i][j]=temp-dungeon[i][j]\,\,if\,\,temp-dungeon[i][j]>0\,\,else\,\,1$$

代码如下：

public int calculateMinimumHP(int[][] dungeon) {
        int m=dungeon.length;
        int n=dungeon[0].length;
        int dp[][]=new int[m][n];//记录最小的能量
        int temp;
        for(int i=m-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                if(i==m-1&&j==n-1)dp[i][j]=dungeon[i][j]>0?1:1-dungeon[i][j];
                else if(i==m-1)dp[i][j]=(temp=dp[i][j+1]-dungeon[i][j])>0?temp:1;
                else if(j==n-1)dp[i][j]=(temp=dp[i+1][j]-dungeon[i][j])>0?temp:1;
                else dp[i][j]=(temp=Math.min(dp[i+1][j],dp[i][j+1])-dungeon[i][j])>0?temp:1;
            }
        }
        return dp[0][0];
    }