本文共 6208 字，大约阅读时间需要 20 分钟。

背包问题

• 问题描述与解决思路
  
• 代码

public class Solution {
       /**     * @param m: An integer m denotes the size of a backpack     * @param A: Given n items with size A[i]     * @param V: Given n items with value V[i]     * @return: The maximum value     */    public int backPackII(int m, int[] A, int[] V) {
           // write your code here        /*        if (m == 0) return 0;        if (A == null || V == null) return 0;        if (A.length == 0 || V.length == 0) return 0;                //构建二维数组存放最大值        int[][] answers = new int[A.length + 1][m + 1];                //java在初始化数组的时候已经默认全填充为0        //所以直接按第二行第二列开始运算即可        //行表示放的第几个物品        //列表示此时包的大小        for (int row = 1; row < answers.length; row++) {            for (int col = 1; col < m + 1; col ++) {                if (col >= A[row - 1]) {                    //放的下                    answers[row][col] = Math.max(V[row - 1] + answers[row - 1][col - A[row - 1]], answers[row - 1][col]);                } else {                    //表示放不下                    answers[row][col] = answers[row - 1][col];                }            }        }        //返回最后一个数据        return answers[A.length][m];        */        //方法二优化内存        if (m == 0) return 0;        if (A == null || V == null) return 0;        if (A.length == 0 || V.length == 0) return 0;        //只用一维数组表示上一行的情况就行        //这个数组的长度就是包的最大值加一        int[] answers = new int[m + 1];        //还是从第一个物品开始计算        for (int row = 1; row < A.length + 1; row++) {
               //在判断放下放不下的时候因为我们保保存的是一行数据            //所以要从后往前遍历            for (int col = m; col >= 1; col--) {
                   if (col >= A[row - 1]) {
                       //表示放的下                    answers[col] = Math.max(V[row - 1] + answers[col - A[row - 1]], answers[col]);                }            }        }        return answers[m];            }}

回文串分割(Palindrome Partitioning)

• 问题描述与解决思路
  
• 代码

//回文串分割(Palindrome Partitioning)    public int minCut(String s) {
           if (s == null) return 0;        if (s.length() == 0) return 0;        //设置一个一维数组保存f[i]        int[] f = new int[s.length() + 1];        for (int i = 0; i < f.length; i++) {
               //初始化f[i]等于当前字符串最大分割次数            f[i] = i - 1;        }        //index表示index下标前的字符串        for (int index = 1; index <= s.length(); index++) {
               //i表示模拟分割的地方 为了方便看整体 i应该模拟分割从0开始            for (int i = 0; i < index; i++) {
                   if (isHuiWen(s, i, index - 1)) {
                       f[index] = Math.min(f[index], f[i] + 1);                }            }        }        return f[s.length()];    }    private boolean isHuiWen(String s, int start, int end) {
           while (start < end) {
               if (s.charAt(start) != s.charAt(end)) {
                   return false;            }            start++;            end--;        }        return true;    }

编辑距离(Edit Distance)

• 问题描述与解决思路
  
• 代码

//编辑距离(Edit Distance)    public int minDistance(String word1, String word2) {
                   if (word1 == null && word2 == null) return 0;        if (word1 == null || word1.length() == 0) {
               return word2.length();        }        if (word2 == null || word2.length() == 0) {
               return word1.length();        }                int len1 = word1.length();        int len2 = word2.length();        //初始化一个二维数组        int[][] answers = new int[len1 + 1][len2 + 1];        //初始化第一列的数据        for (int i = 0; i < len1 + 1; i++) {
               answers[i][0] = i;        }        //初始化第一行的数据        for (int i = 0; i < len2 + 1; i++) {
               answers[0][i] = i;        }        //从第二行第二列开始看起        for (int row = 1; row < len1 + 1; row++) {
               for (int col = 1; col < len2 + 1; col++) {
                   answers[row][col] = Math.min(answers[row - 1][col], answers[row][col]) + 1;                //判断字符是不是相同                if (word1.charAt(row - 1) == word2.charAt(col - 1)) {
                       //当前字符相同                    answers[row][col] = Math.min(answers[row][col], answers[row - 1][col - 1]);                } else {
                       //当前字符不相等, 还需要在变换一次                    answers[row][col] = Math.min(answers[row][col], answers[row - 1][col - 1] + 1);                }            }        }        return answers[len1][len2];    }

不同子序列(Distinct Subsequences)

• 问题描述与解题思路
  
• 代码

public class Solution {
       /**     * 不同子序列(Distinct Subsequences)     * @param S     * @param T     * @return     */    public int numDistinct(String S, String T) {
           if (T == null && S == null) return 1;        if (S == null || S.length() == 0) return 0;        if (T == null || T.length() == 0) return 1;        int len1 = S.length();        int len2 = T.length();        //构建二维数组        int[][] answers = new int[len1 + 1][len2 + 1];        //第一行表示S为空 所以是0        //第一列表示T为空 所以是1        for (int i = 0; i < len1 + 1; i++) {
               answers[i][0] = 1;        }        //从第二行第二列开始计算数目        for (int row = 1; row < len1 + 1; row++) {
               for (int col = 1; col < len2 + 1; col++) {
                   //判断当前字符是不是相等                if (S.charAt(row - 1) == T.charAt(col - 1)) {
                       //表示相等                    answers[row][col] = answers[row - 1][col - 1] + answers[row - 1][col];                } else {
                       //表示不相等                    answers[row][col] = answers[row - 1][col];                }            }        }        return answers[len1][len2];    }    //内存优化    public int numDistinct2(String S, String T) {
           if (T == null && S == null) return 1;        if (S == null || S.length() == 0) return 0;        if (T == null || T.length() == 0) return 1;        //构建一个一维数组长度是T的长度加一        int[] answers = new int[T.length() + 1];        //第一个数字设置为1其余为0        answers[0] = 1;        //从第二行第二列开始看起        for (int row = 1; row < S.length()+ 1; row++) {
               //为了不影响前面数据计算 必须从后往前计算            for (int col = T.length(); col > 0; col--) {
                   //这里的操作还是判断当前字符是不是相等                if (S.charAt(row - 1) == T.charAt(col - 1)) {
                       //当前字符相等                    answers[col] += answers[col - 1];                }            }        }        return answers[T.length()];    }}

转载地址：http://njsci.baihongyu.com/