目录

第1题 Fibonacci

第2题 字符串分割(Word Break)

.第3题 三角矩阵(Triangle)

第4题 路径总数(Unique Paths)

第5题 最小路径和(Minimum Path Sum)

第6题 背包问题

第7题 回文串分割(Palindrome Partitioning)

第8题 编辑距离(Edit Distance)

第9题 不同子序列(Distinct Subsequences)

---

第1题 Fibonacci

分析问题:

1. 状态定义F(i):第i个项的值

2. 状态间的转移方程定义:F(i)=F(i-1)+F(i-2)

3. 状态的初始化:F(0)=0 F(1)=1

4. 返回结果:F(i)

public class Solution {public int Fibonacci(int n) {//创建数组,保存状态的值int[] dp=new int[n+1];dp[0]=0;dp[1]=1;//F(i)=F(i-1)+F(i-2)//从第二个开始到第n个结束for(int i=2;i<=n;i++){dp[i]=dp[i-1]+dp[i-2];}return dp[n];}
}

第2题 字符串分割(Word Break)

F(i)   F(j) && [j+1,i]  可以在词典中找到

分析问题:

1. 状态定义F(i):

       字符串s是否可以分割

2. 状态间的转移方程定义:

        F(i):(j<i) && F(j) $$ [j+1,i] 是否可以在词典中找到

3. 状态的初始化:

             F(0)=true

4. 返回结果:

        F(字符串长度):f(s.size())

public class Solution {public boolean wordBreak(String s, Set<String> dict) {boolean[] dp=new boolean[s.length()+1];dp[0]=true;for(int i=1;i<=s.length();i++){for(int j=0;j<i;j++){if(dp[j] && dict.contains(s.substring(j,i))){dp[i]=true;break;}}}return dp[s.length()];}
}

.第3题 三角矩阵(Triangle)

问题:从顶部到底部的最小路径和

状态:从(0,0)到(i,j)的最小路径和

状态转移方程:

(0

F(i,j): min(F(i-1,j-1),F(i-1,j))+array[i][j] 前一个最小的和当前的值的和

(j==0 || j==i):F(i,j):

j==0 ; (F(i-1,0)+array[i][0]

j==i;F(i-1,j-1)+array[i][j]

初始状态:

F(0,0)=array[0][0]

返回结果:

min(F(row-1,j))

public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {if(triangle.isEmpty()){return 0;}List<List<Integer>> minPathSum=new ArrayList<>();for(int i=0;i<triangle.size();i++){minPathSum.add(new ArrayList<>());}//F(0)(0)初始化minPathSum.get(0).add(triangle.get(0).get(0));for(int i=1;i<triangle.size();i++){int curSum=0;for(int j=0;j<=i;j++){if(j==0){curSum=minPathSum.get(i-1).get(0);}else if(j==i){curSum=minPathSum.get(i-1).get(j-1);}else{curSum=Math.min(minPathSum.get(i-1).get(j),minPathSum.get(i-1).get(j-1));}//之前的值加当前的值minPathSum.get(i).add(triangle.get(i).get(j)+curSum);}}int size=triangle.size();//值为最后一行第一个int allMin=minPathSum.get(size-1).get(0);for (int i = 1; i < size; i++) {//遍历最后一行找到最小值allMin=Math.min(allMin,minPathSum.get(size-1).get(i));}return allMin;
}

第4题 路径总数(Unique Paths)

 

状态:从(0,0)到任意一点的个数

转移方程:F(i,i)=F(i-1,j)+F(i,j-1);   上面和左面的个数和

初识状态:F(i,0)=F(0,j)=1;

返回结果: F(m-1,n-1)

 public int uniquePaths (int m, int n) {int[][] arr=new int[m][n];//初始化for(int i=0;i<m;i++){arr[i][0]=1;}for(int i=0;i<n;i++){arr[0][i]=1;}//过程for(int i=1;i<m;i++){for(int j=1;j<n;j++){arr[i][j]=arr[i-1][j]+arr[i][j-1];}}return arr[m-1][n-1];}

第5题 最小路径和(Minimum Path Sum)

状态: 从(0,0)到(i,j)的最短路径和

状态转移方程:F(i,j)=min{F(i-1,j),,F(i,j-1)}+array[i][j]

                       i==0   F=F(0,j-1)+array[0][j]

                         j==0 F(i-1,0)+array[i][j]

初始化   F(0,0)=array[0][0]

返回结果:F(m-1,n-1)

public int minPathSum (int[][] grid) {int n=grid.length;int m=grid[0].length;if(n==0 || m==0){return 0;}//在grid的基础上改for(int i=1;i<n;i++){grid[i][0]=grid[i-1][0]+grid[i][0];}for(int i=1;i<m;i++){grid[0][i]=grid[0][i-1]+grid[0][i];}for(int i=1;i<n;i++){for(int j=1;j<m;j++){grid[i][j]=Math.min(grid[i-1][j],grid[i][j-1])+grid[i][j];}}return grid[n-1][m-1];}

第6题 背包问题

 

状态:F(i,j):从前I个商品中选择,包的大小为j时,最大值

状态转移方程:

      1.能放入:

                1.不放:和前一个相同

                 2.放入:大小剪去改商品的大小,价值增加

      2.不能放入: 

               和前一个相同

初识状态:

         第0行和第0列都为0,表示 没有商品或者包大小为0

       F(0,j)=F(i,0)=0;

     返回结果F(m,n)

 public int backPackII(int m, int[] a, int[] v) {//得到商品总个数//包大小为0,或没有商品直接返回//创建二维数组:表示背包总价值   列表示放入的商品个数  行表示包的大小//初始化  行为0,或列为0,结果都为0//过程  判断商品大小,有放入和不放入两种//返回int num=a.length;if(m==0 || num==0){return 0;}// 0,0返回,所以要+1int[][] dp=new int[num+1][m+1];for(int i=0;i<=num;i++){dp[i][0]=0;}for(int i=0;i<=m;i++){dp[0][i]=0;}//从1到num开始遍历for(int i=1;i<=num;i++){for(int j=1;j<=m;j++){//a,v数组是从0开始的//dp从1开始if(a[i-1]>j){dp[i][j]=dp[i-1][j];}else{int cur=dp[i-1][j-a[i-1]]+v[i-1];dp[i][j]=Math.max(cur,dp[i-1][j]);}}}return dp[num][m];

第7题 回文串分割(Palindrome Partitioning)

  如果从j+1到i为回文串,也知道j之前的分割次数,就在切一次,保证都是回文串

       F(i):[i,i]是回文串:0

              j<i && [j+1][i]是回文串:min(f(i)+1)

 

状态:f(i):s的前i个字符最小的分割次数

状态转移方程:

    如果j到i-1是是回文串,f(j)+1

F(i,j):

初始状态:

        f(i)=i-1  从1开始  最大分割次数为每一个字母都分割一次

循环判断首尾元素是否相同，如果全部相同，则是回文串

import java.util.*;public class Solution {/*** * @param s string字符串 * @return int整型*/public int minCut (String s) {int len=s.length();if(len==0){return 0;}int[] minCut=new int[len+1];//初始化for(int i=0;i<=len;i++){minCut[i]=i-1;}for (int i = 1; i <=len ; i++) {for (int j = 0; j <=i ; j++) {//前面的循环就直接可以拿到0-j是不是回文串的结果//前面的结果是已知的,要判断后面的是不是回文串if(isPal(s,j,i-1)){minCut[i]=Math.min(minCut[i],minCut[j]+1);}}}return minCut[len];}private boolean isPal(String s, int start, int end) {while(start<end){if(s.charAt(start)!=s.charAt(end)){return false;}start++;end--;}return true;
}
}

第8题 编辑距离(Edit Distance)

 

问题:word1到word2的编辑距离

子问题:word1局部到word2局部的编辑距离

状态：

F(i,j):word1前i个字符到word2前j个字符的编辑距离

min(删除,插入,替换(相等不加一))

F(i,j) = min { F(i-1,j）+1, F(i,j-1) +1, F(i-1,j-1) +(w1[i]==w2[j]?0:1) }

                      i删除             增加i           如果i,j对应的字符相等,不操作,如果不相等,+1

初始化:F(i,0)=i

            F(0,i)=i

返回结果:F(m,n)

步骤:

1. 有一个为空,返回另一个的长度
2. 初始化   
3. 状态变化:从1开始
   1. 得到插入和删除的最小值
   2. 判断i,j对应的元素是否相等
   3. 替换和1得到的值取最小值
4. 返回

import java.util.*;public class Solution {/*** * @param word1 string字符串 * @param word2 string字符串 * @return int整型*/public int minDistance (String word1, String word2) {// write code hereif(word1.isEmpty() || word2.isEmpty()){return Math.max(word1.length(),word2.length());}int row=word1.length();int col=word2.length();int[][] dp=new int[row+1][col+1];for(int i=0;i<=row;i++){dp[i][0]=i;}for(int i=0;i<=col;i++){dp[0][i]=i;}for(int i=1;i<=row;i++){for(int j=1;j<=col;j++){int cur=Math.min(dp[i-1][j],dp[i][j-1])+1;if(word1.charAt(i-1) ==word2.charAt(j-1)){dp[i][j]=Math.min(dp[i-1][j-1],cur);}else{dp[i][j]=Math.min(dp[i-1][j-1]+1,cur);}}}return dp[row][col];}
}

第9题 不同子序列(Distinct Subsequences)

 

1. 问题:
   1. S中和T相同的子序列的个数
2. 子问题:
   1. S的子串中和T相同的子序列的个数
3. 状态F(i):
   1. S的前i个字符构成的子串中和T相同的子序列的个数
   2. 子串长度>=T的长度
   3. 在F(i,j)处需要考虑S[i] = T[j] 和 S[i] != T[j]两种情况
4. 状态转移方程
   1. 当s[i]!=T[j]:   F(i,j)=F(i-1,j)
   2. 当s[i]==T[i]:
      1. 匹配: F(i,j)=F(i-1,j-1)
      2. 不匹配: F(i,j)=F(i-1,j)     s,t下标从0开始
5. 初始化:
   1. F(i,0)=1  s中包含空集
   2. F(0,j)=0  空集中不包含

import java.util.*;public class Solution {/*** * @param S string字符串 * @param T string字符串 * @return int整型*/public int numDistinct (String S, String T) {int slen=S.length();int tlen=T.length();//初始化int[][] dp=new int[slen+1][tlen+1];dp[0][0]=1;for(int i=1;i<=slen;i++){dp[i][0]=1;}for(int i=1;i<=tlen;i++){dp[0][i]=0;}for(int i=1;i<=slen;i++){for(int j=1;j<=tlen;j++){if(S.charAt(i-1)==T.charAt(j-1)){dp[i][j]=dp[i-1][j-1]+dp[i-1][j];}else{dp[i][j]=dp[i-1][j];}}}return dp[slen][tlen];}
}