题目一：兑换零钱（一）

题目描述：

给定数组coins，coins中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数

输入输出描述：

输入：[5,2,3],20              返回值：4                             说明：将面值为5的货币使用4张

输入：[5,2,3],0               返回值：0                              说明：不需要任何货币都能凑够0元
输入：[3,5],2                  返回值：-1                             说明：不可能实现的情况（aim<最小货币）

题目解析：

step1：定义dp[i]表示凑够i元的最小货币数。返回值应该是dp[aim],dp数组的范围是0<=i<aim+1

step2:刚开始都设置成最大值。假设货币最小为1，凑够aim元最多需要aim张，则将dp数组全部初始化为aim+1 

step3：初始化dp[0]=0;  凑够0元需要0张

step3：遍历整个dp数组。

step4：在dp数组里再遍历coins数组

           ①当前面值coin>i，跳过continue；

           ②当前面值coin<i,   比较dp[i]和dp[i-面值]+1  大小 ，维护最小

step4：dp[aim]的值是否超过aim，如果超过说明无解，否则返回即可。

作答情况：

没有将dp数组里面的值刚开始设置为最大值，带来了很多麻烦。

其实将dp[aim]的值最开始设置为最大aim+1，到算法结束之后直接判断dp[aim]是否超过aim，如果超过说明无解，否则返回即可。

代码：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 最少货币数
     * @param arr int整型一维数组 the array
     * @param aim int整型 the target
     * @return int整型
     */
    public int minMoney (int[] coins, int aim) {
        //dp[i] 表示凑够i元的最小货币数
        int[] dp = new int[aim + 1];
        //全设置为最大值
        Arrays.fill(dp, aim + 1);
        //初始化
        dp[0] = 0;
        //遍历整个数组，便于递归
        for (int i = 1; i <= aim; i++) {

            for (int coin : coins) {
                //当前面值>目标钱数,   不考虑，走下一个
                if (coin > i ) continue;
                //当前面值< 目标钱数，  递归，并维护最小值
                dp[i] = Math.min(dp[i], dp[i - coin] + 1);
            }
        }
        //dp[aim]的值是否超过aim，如果超过说明无解，否则返回即可。
        return dp[aim] == aim + 1 ? -1 : dp[aim];
    }
}

题目二：最长回文子串

题目描述：

对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。

输入输出描述：

输入："ababc"                   返回值：3
说明：最长的回文子串为"aba"与"bab"，长度都为3
输入："abbba"                  返回值：5
说明：最长的回文子串为"abbba"，长度为3
输入："b"                           返回值：1

题目解析：

step1：dp[i][j]为判断从i到j是不是回文子串，设置返回值为boolean类型的

step2：初始化结果result为1（每个字符至少是自己的回文子串，初始化长度为1）

step3：初始化dp数组（遍历数组，每个字符至少是自己的回文子串，dp[i][i]为true）

step4：设置右边界i从第二个元素开始遍历，左边界j范围为0至i-1。

step5：i下标对应的元素==j下表对应的元素，并且元素相邻或者i+1到j-1是回文子串（继续dp），返回true，并且在判定回文子串是true时立即更新最大值。

作答情况：

result更新值时写到了if语句外面。

代码：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param A string字符串 
     * @return int整型
     */
    public int getLongestPalindrome (String str) {
        int m=str.length();
        //每个字符至少是自己的回文子串
        int result=1;
        //dp[i][j]表示字符串从i到j是回文子串
        boolean[][] dp=new boolean[m][m];
        for(int i=0;i<m;i++){
            //每个字符都是自己的回文子串
           dp[i][i]=true;
        }
        //从第二个元素开始，规定字符串的范围
          for(int j=1;j<m;j++){
            for(int i=j-1;i>=0;i--){
                //j为最右边，i为最左边
                //i下标对应的元素==j下表对应的元素并且元素相邻或者i+1到j-1是回文子串，返回true，并且保存最长值
                if(str.charAt(i)==str.charAt(j)&&(j-i==1||dp[i+1][j-1])){
                    dp[i][j]=true;
                    result=Math.max(result,j-i+1);
                }
            }
          }
        return  result;
    }
}

题目二：编辑距离（一）

题目描述：

给定两个字符串 str1 和 str2 ，请你算出将 str1 转为 str2 的最少操作数。

你可以对字符串进行3种操作：

1.插入一个字符

2.删除一个字符

3.修改一个字符。

字符串长度满足 1≤n≤1000  ，保证字符串中只出现小写英文字母。

输入输出描述：

输入："nowcoder","new"          返回值：6

说明："nowcoder"=>"newcoder"(将'o'替换为'e')，修改操作1次
           "nowcoder"=>"new"(删除"coder")，删除操作5次    

 
输入："intention","execution"     返回值：5
说明：因为2个长度都是9，后面的4个后缀的长度都为"tion"，于是从"inten"到"execu"逐个修改

输入："now","nowcoder"         返回值：5

说明：逐个删除“coder”

题目解析：

step1：dp[i][j]表示str1的前i个字符转化为str2的前j个字符的最小操作数，设置dp数组的大小一定要大于str1和  str2的长度。

step2：特殊情况判定

           ①str1为空字符串，dp[0][j]=j  (将str1插入str2的前j个所有字符要进行j次)

            ②str2为空字符串，dp[i][0]=i  (将str1转化为空字符串要进行i次删除操作)

step3：dp从各自从第1个字符开始，规定dp第一个下标为1，循环遍历两个str字符串

step4：判定当前字符是否相等

            ①当前字符相等（不用操作），递归到前i-1个字符转化为前j-1个字符最小操作数，即

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

            ②当前字符不相等（需要根据情况操作）

               例如pre->er
              插入：pre->e (e)   pre的前3个字符转化为er的前1个字符，得到e，再插入r（1次操作）
              删除：pr->er(ere) pre的前2个字符转化为er的前2个字符，得到ere，再删除e（1次操作）
              修改：pr->e(ee) pre的前2个字符转化为er的前1个字符，得到ee，再修改e为r(1次操作）

step5：最后比较这三种操作，维护最小值

作答情况：

通过测试用例。

①当前字符不相等的情况，如果没有思路，可以经过举例来思考；

②三个元素比较大小，一定是两两比较，Math函数只能存两个结果值进行比较。

代码：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str1 string字符串 
     * @param str2 string字符串 
     * @return int整型
     */
    public int editDistance (String str1, String str2) {
        //dp[i][j] 将str1的前i个字符转化为str2的前j个字符
        int m=str1.length();
        int n=str2.length();
        int[][] dp=new int[m+1][n+1];
        for(int i=0;i<=m;i++){
            dp[i][0]=i;
        }
        for(int j=0;j<=n;j++){
            dp[0][j]=j;
        }
        //dp从各自从第1个字符开始
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                //dp中下标从1开始，str下标从0开始
         //当前字符相等（不用操作），递归到前i-1个字符转化为前j-1个字符最小操作数
                if(str1.charAt(i-1)==str2.charAt(j-1)) dp[i][j]=dp[i-1][j-1];
                //当前字符不相等（需要根据情况操作）
                else{
//例如pre->er
 //插入：pre->e (e)   pre的前3个字符转化为er的前1个字符，得到e，再插入r（1次操作）
 //删除：pr->er(ere) pre的前2个字符转化为er的前2个字符，得到ere，再删除e（1次操作）
 //修改：pr->e(ee) pre的前2个字符转化为er的前1个字符，得到ee，再修改e为r(1次操作）

 //最后比较这三种操作，维护最小值
                    dp[i][j]=Math.min(dp[i][j-1],
                    Math.min(dp[i-1][j],dp[i-1][j-1])
                    )+1;
                }
            }
        }
        return dp[m][n];
    }
}