算法之美——动态规划

作者: 康凯森

日期: 2016-11-19

分类: 算法

什么情况考虑动态规划

  • 求最大值最小值
  • 判断是否可行
  • 统计方案个数

什么情况下不考虑动态规划

  • 求出所有具体的方案而非方案个数
  • 输入数据是一个集合而不是 序列

动态规划的实现方式

多重循环

  • 优点：正规，存在空间优化的可能
  • 缺点：思考有难度
  • 实现方式： 自底向上 和 自顶向下

记忆化搜索

  • 优点：容易从搜索算法直接 转化过来
  • 缺点：递归

动态规划的四要素

状态 State

存储小规模问题的结果

方程 Function

状态之间的联系,怎么通过小的状态,来算大的状态

初始化 Initialization

最极限的小状态是什么, 起点。

初始化一个二维的动态规划时 就去初始化第0行和第0列。

如果不是跟坐标相关的动态规划 一般有N个数/字符,就开N+1个位置的数组 第0个位置单独留出来作初始化。

答案 Answer

最大的那个状态是什么,终点。

坐标型动态规划

state:
f[x] 表示我从起点走到坐标x
f[x][y] 表示我从起点走到坐标x,y
function: 研究走到x,y这个点之前的一步 
intialize: 起点
answer: 终点

单序列动态规划

state: f[i]表示前i个位置/数字/字母等
function: f[i] = f(f[j]) j是i之前的一个位置 
initialize: f[0]
answer: f[n-1]

双序列动态规划

state: f[i][j]代表了第一个sequence的前i个数字/字符,配上第二个sequence 的前j个
function: f[i][j] = 研究第i个和第j个的匹配关系
initialize: f[i][0] 和 f[0][i]
answer: f[s1.length()][s2.length()]

数字三角形 triangle

// version 0: top-down
public class Solution {
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
    public int minimumTotal(int[][] triangle) {
        if (triangle == null || triangle.length == 0) {
            return -1;
        }
        if (triangle[0] == null || triangle[0].length == 0) {
            return -1;
        }

        // state: f[x][y] = minimum path value from 0,0 to x,y
        int n = triangle.length;
        int[][] f = new int[n][n];

        // initialize 
        f[0][0] = triangle[0][0];
        for (int i = 1; i < n; i++) {
            f[i][0] = f[i - 1][0] + triangle[i][0];
            f[i][i] = f[i - 1][i - 1] + triangle[i][i];
        }

        // top down
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < i; j++) {
                f[i][j] = Math.min(f[i - 1][j], f[i - 1][j - 1]) + triangle[i][j];
            }
        }

        // answer
        int best = f[n - 1][0];
        for (int i = 1; i < n; i++) {
            best = Math.min(best, f[n - 1][i]);
        }
        return best;
    }
}


//Version 1: Bottom-Up
public class Solution {
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
    public int minimumTotal(int[][] triangle) {
        if (triangle == null || triangle.length == 0) {
            return -1;
        }
        if (triangle[0] == null || triangle[0].length == 0) {
            return -1;
        }

        // state: f[x][y] = minimum path value from x,y to bottom
        int n = triangle.length;
        int[][] f = new int[n][n];

        // initialize 
        for (int i = 0; i < n; i++) {
            f[n - 1][i] = triangle[n - 1][i];
        }

        // bottom up
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                f[i][j] = Math.min(f[i + 1][j], f[i + 1][j + 1]) + triangle[i][j];
            }
        }

        // answer
        return f[0][0];
    }
}


//Version 2 : Memorize Search
public class Solution {
    private int n;
    private int[][] minSum;
    private int[][] triangle;

    private int search(int x, int y) {
        if (x >= n) {
            return 0;
        }

        if (minSum[x][y] != Integer.MAX_VALUE) {
            return minSum[x][y];
        }

        minSum[x][y] = Math.min(search(x + 1, y), search(x + 1, y + 1))
            + triangle[x][y];
        return minSum[x][y];
    }

    public int minimumTotal(int[][] triangle) {
        if (triangle == null || triangle.length == 0) {
            return -1;
        }
        if (triangle[0] == null || triangle[0].length == 0) {
            return -1;
        }

        this.n = triangle.length;
        this.triangle = triangle;
        this.minSum = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                minSum[i][j] = Integer.MAX_VALUE;
            }
        }

        return search(0, 0);
    }
}

最小路径和 minimum-path-sum

public class Solution {
    /**
     * @param grid: a list of lists of integers.
     * @return: An integer, minimizes the sum of all numbers along its path
     */
    public int minPathSum(int[][] grid) {
        int n = grid.length;
        int m = grid[n-1].length;
        // state: minSum[x][y] = minimum path value from 0,0 to x,y
        int[][] minSum = new int[n][m];

        // initialize 
        minSum[0][0] = grid[0][0];
        for (int i = 1; i < n; i++) {
            minSum[i][0] = minSum[i - 1][0] + grid[i][0];
        }
        for (int i = 1; i < m; i++) {
            minSum[0][i] = minSum[0][i - 1] + grid[0][i];
        }
        //Function
        for (int i = 1; i < n;i++){
            for (int j= 1; j < m;j++){
                minSum[i][j] = Math.min(minSum[i][j-1],minSum[i-1][j]) + grid[i][j];
            }
        }
        //Answer
        return minSum[n-1][m-1];
    }
}

不同的路径 unique-paths

public class Solution {
    /**
     * @param n, m: positive integer (1 <= n ,m <= 100)
     * @return an integer
     */
    public int uniquePaths(int m, int n) {
        if (m == 0 || n == 0) {
            return 0;
        }
        // state: count[x][y] = from 0,0 to x,y 路径条数
        int[][] count = new int[m][n];
        // initialize 
        for (int i = 0; i < m; i++){
            count[i][0] = 1;
        }
        for (int i = 0; i < n; i++){
            count[0][i] = 1;
        }
        //Function
        for (int i = 1; i < m; i++){
            for (int j = 1; j < n; j++){
                count[i][j] = count[i-1][j] + count[i][j-1];
            }
        }
        //Answer
        return count[m-1][n-1];
    }
}

不同的路径 II unique-paths-ii

public class Solution {
    /**
     * @param obstacleGrid: A list of lists of integers
     * @return: An integer
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // write your code here
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;
        int[][] count = new int[n][m];
        if (obstacleGrid[0][0] == 1 || obstacleGrid[n-1][m-1] == 1)
            return 0;
        else 
            count[0][0] = 1;
        for (int i = 1; i < n; i++){
            if (obstacleGrid[i-1][0] == 0)
                count[i][0] = 1;
            else
                break;
        }
        for (int i = 1; i < m; i++){
            if (obstacleGrid[0][i-1] == 0)
                count[0][i] = 1;
            else
                break;

        }
        for (int i = 1; i < n; i++){
            for (int j = 1; j < m; j++){
                if (obstacleGrid[i-1][j] == 1 && obstacleGrid[i][j-1] == 1)
                    count[i][j] = 0;
                else if (obstacleGrid[i-1][j] == 1)
                    count[i][j] = count[i][j-1];
                else if (obstacleGrid[i][j-1] == 1)
                    count[i][j] = count[i-1][j];
                else
                    count[i][j] = count[i-1][j] + count[i][j-1];
            }
        }
        return count[n-1][m-1];
    }
}

爬楼梯 climbing-stairs

public class Solution {
    /**
     * @param n: An integer
     * @return: An integer
     */
    public int climbStairs(int n) {
        // write your code here
        if (n <= 1) {
            return 1;
        }
        int a1 = 1;
        int a2 = 1;
        int a3 = 0;
        for (int i = 2; i <= n; i++){
            a3 = a1 + a2;
            a1 = a2;
            a2 = a3;
        }
        return a3;
    }
}

跳跃游戏 jump-game

public class Solution {
    /**
     * @param A: A list of integers
     * @return: The boolean answer
     */
    public boolean canJump(int[] A) {
        // wirte your code here
        int n = A.length;
        boolean[] can = new boolean[n];
        can[0] = true;
        for (int i = 1; i < n; i++){
            for (int j = 0; j < i; j++){
                if (can[j] && A[j] >= (i - j)){
                    can[i] = true;
                    break;
                }
            }
        }
        return can[n-1];
    }
}

跳跃游戏2 jump-game-ii

public class Solution {
    /**
     * @param A: A list of lists of integers
     * @return: An integer
     */
    public int jump(int[] A) {
        // write your code here
        int n = A.length;
        //count[i]代表到达当前位置需要几步
        int[] count = new int[n];
        // initialize 
        count[0] = 0;
        //Function
        for (int i = 1; i < n; i++){
            count[i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++){
                if (count[j] != Integer.MAX_VALUE && A[j] >= i - j){
                    count[i] = count[j] + 1;
                    break;
                }
            }
        }
        //Answer
        return count[n-1];
    }
}

分割回文串 II palindrome-partitioning-ii

public class Solution {
    /**
     * @param s a string
     * @return an integer
     */

    private boolean isPalindrome(String s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }

    private boolean[][] getIsPalindrome(String s) {
        boolean[][] isPalindrome = new boolean[s.length()][s.length()];

        for (int i = 0; i < s.length(); i++) {
            isPalindrome[i][i] = true;
        }
        for (int i = 0; i < s.length() - 1; i++) {
            isPalindrome[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
        }

        for (int length = 2; length < s.length(); length++) {
            for (int start = 0; start + length < s.length(); start++) {
                isPalindrome[start][start + length]
                    = isPalindrome[start + 1][start + length - 1] && s.charAt(start) == s.charAt(start + length);
            }
        }

        return isPalindrome;
    }


    public int minCut(String s) {
        // write your code here
        if (s == null || s.length() == 0) {
            return 0;
        }

        // preparation
        //boolean[][] isPalindrome = getIsPalindrome(s);

        // initialize
        int[] f = new int[s.length() + 1];
        for (int i = 0; i <= s.length(); i++) {
            f[i] = i - 1;
        }

         //Function
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (isPalindrome(s,j,i-1)) {
                    f[i] = Math.min(f[i], f[j] + 1);
                }
            }
        }
         //Answer
        return f[s.length()];
    }
};

单词切分 word-break

public class Solution {
    /**
     * @param s: A string s
     * @param dict: A dictionary of words dict
     */
    private int getMaxLength(Set<String> dict) {
        int maxLength = 0;
        for (String word : dict) {
            maxLength = Math.max(maxLength, word.length());
        }
        return maxLength;
    }
    public boolean wordBreak(String s, Set<String> dict) {
        // write your code here   
        if (s == null || dict == null ) {
            return false;
        }
        if (s.length() == 0 && dict.isEmpty()) {
            return true;
        }
        if (s.length() == 0 || dict.isEmpty()) {
            return false;
        }
        int n = s.length();
        int maxLength = getMaxLength(dict);
        //can[i] 表示前i个字符是否可以被切分
        boolean[] can = new boolean[n+1];
        can [0] = true;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= maxLength && j <= i; j++) {
                if (can[i - j] && dict.contains(s.substring(i-j,i))) {
                    can[i] = true;
                    break;
                }
            }
        }
        return can[n];
    }
}

最长上升子序列 longest-increasing-subsequence

public class Solution {
    /**
     * @param nums: The integer array
     * @return: The length of LIS (longest increasing subsequence)
     */
    public int longestIncreasingSubsequence(int[] nums) {
        // write your code here
        int n = nums.length;
        //f[i]表示前i个数字中以第i个结尾的LIS的长度
        int[] f =new int[n]; 
        int max = 0;
        for (int i = 0; i < n; i++) {
            f[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] <= nums[i]) {
                    f[i] = f[i] > f[j] + 1 ? f[i] : f[j] + 1;
                }
            }
            if (f[i] > max) {
                max = f[i];
            }
        }
        return max;
    }
}

最长公共子序列 longest-common-subsequence

public class Solution {
    /**
     * @param A, B: Two strings.
     * @return: The length of longest common subsequence of A and B.
     */
    public int longestCommonSubsequence(String A, String B) {
        // write your code here
        if (A == null || B == null || A.length() == 0 || B.length() == 0)
            return 0;
        int lengthA = A.length();
        int lengthB = B.length();
        int[][] l = new int[lengthA + 1][lengthB + 1];

        for (int i = 0; i < lengthA; i++)
            for (int j = 0; j < lengthB; j++){
                if (A.charAt(i) == B.charAt(j))
                    l[i + 1][j + 1] = l[i][j] + 1;
                else
                    l[i + 1][j + 1] = Math.max(l[i + 1][j],l[i][j + 1]);
            }
        return l[lengthA][lengthB];
    }
}

最长公共子串 longest-common-substring

public class Solution {
    /**
     * @param A, B: Two string.
     * @return: the length of the longest common substring.
     */
    public int longestCommonSubstring(String A, String B) {
        // write your code here
        if (A == null || B == null || A.length() <= 0 || B.length() <= 0)
            return 0;
        int lengthA = A.length();
        int lengthB = B.length();
        int[][] l = new int[lengthA + 1][lengthB + 1];
        int result = 0;
        for (int i = 0; i < lengthA; i++) {
             for (int j = 0; j < lengthB; j++) {
                if (A.charAt(i) == B.charAt(j))
                    l[i + 1][j + 1] = l[i][j] + 1;
                else
                    l[i + 1][j + 1] = 0;
                result = Math.max(result , l[i + 1][j + 1]);
            } 
        }
        return result;
    }
}

编辑距离 edit-distance


state: f[i][j]a的前i个字符最少要用几次编辑可以变成b的前j个字符 
public class Solution {
    /**
     * @param word1 & word2: Two string.
     * @return: The minimum number of steps.
     */
    public int minDistance(String A, String B) {
        // write your code here
        if (A == null || B == null )
            return 0;

        int lengthA = A.length();
        int lengthB = B.length();
        int[][] l = new int[lengthA + 1][lengthB + 1];
        for (int i = 0; i < lengthA + 1; i++){
            l[i][0] = i;
        }
        for (int i = 0; i < lengthB + 1; i++){
            l[0][i] = i;
        }
        for (int i = 0; i < lengthA; i++)
            for (int j = 0; j < lengthB; j++){
                if (A.charAt(i) == B.charAt(j))
                    l[i + 1][j + 1] = l[i][j];
                else
                    l[i + 1][j + 1] = min(l[i + 1][j],l[i][j + 1],l[i][j]) + 1;
            }
        return l[lengthA][lengthB];
    }

    private int min(int a, int b, int c){
        int temp = Math.min(a,b);
        int result = Math.min(temp,c);
        return result;
    }
}

不同的子序列


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

public class Solution {
    public int numDistinct(String S, String T) {
        if (S == null || T == null) {
            return 0;
        }

        int[][] nums = new int[S.length() + 1][T.length() + 1];

        for (int i = 0; i < S.length(); i++) {
            nums[i][0] = 1;
        }
        for (int i = 1; i <= S.length(); i++) {
            for (int j = 1; j <= T.length(); j++) {
                nums[i][j] = nums[i - 1][j];
                if (S.charAt(i - 1) == T.charAt(j - 1)) {
                    nums[i][j] += nums[i - 1][j - 1];
                }
            }
        }
        return nums[S.length()][T.length()];
    }
}

交叉字符串

state: f[i][j]表示s1的前i个字符和s2的前j个字符能否交替组成s3的前i+j个字 符
function: 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])

public class Solution {
    /**
     * Determine whether s3 is formed by interleaving of s1 and s2.
     * @param s1, s2, s3: As description.
     * @return: true or false.
     */
    public boolean isInterleave(String s1, String s2, String s3) {
        if (s1.length() + s2.length() != s3.length()) {
            return false;
        }

        boolean [][] interleaved = new boolean[s1.length() + 1][s2.length() + 1];
        interleaved[0][0] = true;

        for (int i = 1; i <= s1.length(); i++) {
            if(s3.charAt(i - 1) == s1.charAt(i - 1) && interleaved[i - 1][0])
                interleaved[i][0] = true;
        }

        for (int j = 1; j <= s2.length(); j++) {
            if(s3.charAt(j - 1) == s2.charAt(j - 1) && interleaved[0][j - 1])
                interleaved[0][j] = true;
        }

        for (int i = 1; i <= s1.length(); i++) {
            for (int j = 1; j <= s2.length(); j++) {
                if(((s3.charAt(i + j - 1) == s1.charAt(i - 1) && interleaved[i - 1][j]))
                    || ((s3.charAt(i + j - 1)) == s2.charAt(j - 1) && interleaved[i][j - 1]))
                interleaved[i][j] = true;
            }
        }

        return interleaved[s1.length()][s2.length()];
    }
}

背包问题 backpack

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
    public int backPack(int m, int[] A) {
        // write your code here
        if (A == null || A.length == 0)
            return 0;
        int n = A.length;
        boolean[][] can = new boolean[n + 1][m + 1];

        can[0][0] = true;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= m; j++) {
                can[i + 1][j] = can[i][j];
                if (j - A[i] >= 0 && can[i][j - A[i]]) {
                    can[i + 1][j] = true;
                }

            }
        }

        for (int i = m; i > 0; i--) {
            if (can[n][i] == true) {
                return  i;
            } 
        }

        return 0;
    }
}

背包问题 II backpack-ii

public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A & V: Given n items with size A[i] and value V[i]
     * @return: The maximum value
     */
    public int backPackII(int m, int[] A, int V[]) {
        // write your code here
        if (A == null || A.length == 0)
            return 0;
        int[][] count = new int[A.length+1][m+1];
        count[0][0] = 0;

        for (int i=1; i<=A.length; i++) {
            for (int j=0; j<=m; j++) {
                count[i][j] = count[i-1][j];
                if (j - A[i-1] >= 0) {
                    count[i][j] = Math.max(count[i-1][j], count[i-1][j-A[i-1]]+V[i-1]);
                }
            }
        }

        return count[A.length][m];
    }
}

最小调整代价

public class Solution {
    /**
     * @param A: An integer array.
     * @param target: An integer.
     */
    public int MinAdjustmentCost(ArrayList<Integer> A, int target) {
        // write your code here
        if (A.size() < 2) return 0;

        int[][] cost = new int[A.size()][100];
        for (int i = 0; i < 100; i++)
            cost[0][i] = Math.abs(A.get(0)-(i+1));

        for (int i=1;i<A.size();i++)
            for (int j=0;j<100;j++){
                cost[i][j]=Integer.MAX_VALUE;
                int diff = Math.abs(A.get(i)-(j+1));
                int upper = Math.min(j+target,99);
                int lower = Math.max(j-target,0);
                for (int k=lower;k<=upper;k++)
                    if (cost[i-1][k]+diff<cost[i][j])
                        cost[i][j]=cost[i-1][k]+diff;
            }

        int res = Integer.MAX_VALUE;
        for (int i=0;i<100;i++)
            if (cost[A.size()-1][i]<res)
                res = cost[A.size()-1][i];
        return res;
    }
}

K 数和

public class Solution {
    /**
     * @param A: an integer array.
     * @param k: a positive integer (k <= length(A))
     * @param target: a integer
     * @return an integer
     */
     public int  kSum(int A[], int k, int target) {
        int n = A.length;
        int[][][] f = new int[n + 1][k + 1][target + 1];
        for (int i = 0; i < n + 1; i++) {
            f[i][0][0] = 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k && j <= i; j++) {
                for (int t = 1; t <= target; t++) {
                    f[i][j][t] = 0;
                    if (t >= A[i - 1]) {
                        f[i][j][t] = f[i - 1][j - 1][t - A[i - 1]];
                    }
                    f[i][j][t] += f[i - 1][j][t];
                } // for t
            } // for j
        } // for i
        return f[n][k][target];
    }
}

买卖股票的最佳时机 IV

class Solution {
    /**
     * @param k: An integer
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int k, int[] prices) {
        if (k == 0) {
            return 0;
        }
        if(prices==null || prices.length==0)  
        return 0;  
        // K 大于 数组一半时， 直接处理
        if (k >= prices.length / 2) {
            int profit = 0;
            for (int i = 1; i < prices.length; i++) {
                if (prices[i] > prices[i - 1]) {
                    profit += prices[i] - prices[i - 1];
                }
            }
            return profit;
        }
        int len = prices.length;  
        int[][] local = new int[len][k+1];       
        int[][] global = new int[len][k+1];     
        for(int i=1; i<len; i++) {  
            int diff = prices[i] - prices[i-1];  
            for(int j=1; j<=k; j++) {  
                local[i][j] = Math.max(global[i-1][j-1]+Math.max(diff,0), local[i-1][j ]+diff);  
                global[i][j] = Math.max(global[i-1][j], local[i][j]);  
            }  
        }  
        return global[len-1][k];   
    }
};

最大子数组 III ?

public class Solution {
    /**
     * @param nums: A list of integers
     * @param k: An integer denote to find k non-overlapping subarrays
     * @return: An integer denote the sum of max k non-overlapping subarrays
     */
    public int maxSubArray(int[] nums, int k) {
        // write your code here
        if (nums == null)
            return 0;
        int len = nums.length;
        if (len < k)
            return 0;
        //k partitions of array with length len
        int[][] globalMax = new int[k + 1][len + 1];
        for (int i = 1; i <= k; i++) {
            int localMax = Integer.MIN_VALUE;
            //array with length less than i cannot be partitioned
            for (int j = i - 1; j < len; j++) {
                localMax = Math.max(localMax, globalMax[i - 1][j]) + nums[j];
                if (j == i - 1)
                    globalMax[i][j + 1] = localMax;
                else
                    globalMax[i][j + 1] = Math.max(globalMax[i][j], localMax);
            }
        }
        return globalMax[k][len];
    }
}

参考资料

九章算法

《OLAP 性能优化指南》欢迎 Star&共建

《OLAP 性能优化指南》

欢迎关注微信公众号

康凯森