1.1、题目1
剑指 Offer 19. 正则表达式匹配
1.2、解法
动态规划后面再研究
1.3、代码
class Solution {
public boolean isMatch(String s, String p) {
int m = s.length() + 1, n = p.length() + 1;
boolean[][] dp = new boolean[m][n];
dp[0][0] = true;
for(int j = 2; j < n; j += 2)
dp[0][j] = dp[0][j - 2] && p.charAt(j - 1) == '*';
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
dp[i][j] = p.charAt(j - 1) == '*' ?
dp[i][j - 2] || dp[i - 1][j] && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.') :
dp[i - 1][j - 1] && (p.charAt(j - 1) == '.' || s.charAt(i - 1) == p.charAt(j - 1));
}
}
return dp[m - 1][n - 1];
}
}
2.1、题目2
剑指 Offer 49. 丑数
2.2、解法
这题看题解才做出来的，不太懂动态规划，最近研究以下。
2.3、代码
class Solution {
public int nthUglyNumber(int n) {
int a=0,b=0,c=0;
int []dp = new int[n];
dp[0]=1;
for(int i=1;i
3.1、题目3
剑指 Offer 60. n个骰子的点数
3.2、解法
3.3、代码
class Solution {
public double[] dicesProbability(int n) {
double[] dp = new double[6];
Arrays.fill(dp, 1.0 / 6.0);
for (int i = 2; i
Original: https://www.cnblogs.com/cxykhaos/p/15353127.html
Author: 程序员khaos
Title: 剑指offer计划29（动态规划困难）—java
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/714712/
转载文章受原作者版权保护。转载请注明原作者出处！