JZ14 剪绳子_JZ19正则表达式匹配

JZ14 剪绳子

JZ14 剪绳子


import java.util.*;
public class Solution {
    public int cutRope(int target) {
        //动归解决!
        //初始化: dp
        //状态转移: 分为两段的乘积,dp[i-j]*j(j<i) 用已知的dp[i-j]最大长度*j(j<i)
        //状态方程: dp[i] = Math(dp[i],j*dp[i-j]);
        //状态定义: 长度为n可以得到的最大乘积
        //返回结果: dp[target]
        //不超过3直接计算
        if(target <= 3) 
            return target- 1;
        //dp[i]表示长度为i的绳子可以被剪出来的最大乘积
        int[] dp = new int[target + 1];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        dp[4] = 4;    
        //遍历后续每一个长度
        for(int i = 5; i <= target; i++)
            //可以被分成两份
            for(int j = 1; j < i; j++)
                //取最大值
                dp[i] = Math.max(dp[i], j * dp[i - j]);
        return dp[target];
    }
}

这题与以往的动归问题稍有变形,dp[1]...dp[3]初始化结果并不是真正的结果!

因为这里需要乘积!

JZ19正则表达式匹配

JZ19正则表达式匹配


• .解题思路
  • 状态定义： 表示原字符串长度为n，模式串长度为m时，是否能够匹配。
  • 初始化：当原串和模式串都为空时，显然能够匹配， ;当模式串为空，而原串不为空时，均为 。
  • 状态转移：分模式串后一个位置是否为’‘进行讨论,为’‘时，将’‘与前一个位置合并起来进行考虑。如果后一个位置不为’’，并且当前模式串字符和原串字符匹配，则满足 ；如果后一个位置为’*’，
    无论是否匹配，均满足dp[i][j]=dp[i][j-2] (匹配0次)，如果匹配，满足 (匹配1到无穷次或0次)

图示：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */

    public boolean match (String str, String pattern) {
        int n=str.length();
        int m=pattern.length();
        boolean[][] dp=new boolean[n+1][m+1];

        //初始化
        dp[0][0]=true;
        for(int i=1;i<=n;i++){
            dp[i][0]=false;
        }

        //分模式串的后一个位置是否为*进行讨论,为*时，将*与前一个位置合并起来进行考虑
        for(int i=0;i<=n;i++){
            for(int j=1;j<=m;j++){
                if(pattern.charAt(j-1)!='*'){
                    //当前模式串字符和原串字符匹配
                    if(i>0&&(str.charAt(i-1)==pattern.charAt(j-1)||(pattern.charAt(j-1)=='.'))){
                        dp[i][j]=dp[i-1][j-1];
                    }
                }
                else{
                    if(j>=2){
                        //不管是否匹配，都可以将当前字符绑定上*匹配原串字符0次
                        dp[i][j]=dp[i][j-2];
                        //当前模式串字符和原串字符匹配
                        if(i>0&&(str.charAt(i-1)==pattern.charAt(j-2)||(pattern.charAt(j-2)=='.'))){
                            dp[i][j]=dp[i-1][j]||dp[i][j-2];
                        }
                    }
                }
            }
        }
        return dp[n][m];
    }


}

礼物最大价值

连续子数组最大和

public class Solution {
 public int FindGreatestSumOfSubArray(int[] array) {
     //动态规划:
     int Max = array[0];//保存最大值!
     for(int i = 1;i<array.length;i++){
         array[i] = Math.max(array[i-1]+array[i],array[i]);
         Max = Math.max(array[i],Max);
     }
     return Max;
 }
}