动态规划2:题目

绝地灬酷狼 2024-03-16 09:48 147阅读 0赞

目录

第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

023e0787e60d454080346c27af4e41f8.png

分析问题:

  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 {

    1.  public int Fibonacci(int n) {
    2.      //创建数组,保存状态的值
    3.      int[] dp=new int[n+1];
    4.      dp[0]=0;
    5.      dp[1]=1;
    6.      //F(i)=F(i-1)+F(i-2)
    7.      //从第二个开始到第n个结束
    8.      for(int i=2;i<=n;i++){
    9.          dp[i]=dp[i-1]+dp[i-2];
    10.      }
    11.      return dp[n];
    13.  }

    }

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

5ef74c5d312b40eeb24995bcccf103ff.png

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

分析问题:

  1. 状态定义F(i):

字符串s是否可以分割

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

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

  1. 状态的初始化:

F(0)=true

  1. 返回结果:

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

  1. public class Solution {
  2.     public boolean wordBreak(String s, Set<String> dict) {
  3.        boolean[] dp=new boolean[s.length()+1];
  4.        dp[0]=true;
  5.        for(int i=1;i<=s.length();i++){
  6.         for(int j=0;j<i;j++){
  7.             if(dp[j] && dict.contains(s.substring(j,i))){
  8.                 dp[i]=true;
  9.                 break;
  10.             }
  11.         }
  13.        }
  14.        return dp[s.length()];
  16.     }
  17. }

.第3题 三角矩阵(Triangle)

ea06ba98f0c64df2bed0951dec422da3.png

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

状态:从(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))

  1. public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
  2.     if(triangle.isEmpty()){
  3.         return 0;
  4.     }
  6.     List<List<Integer>> minPathSum=new ArrayList<>();
  7.     for(int i=0;i<triangle.size();i++){
  8.         minPathSum.add(new ArrayList<>());
  9.     }
  10.     //F(0)(0)初始化
  11.     minPathSum.get(0).add(triangle.get(0).get(0));
  12.     for(int i=1;i<triangle.size();i++){
  13.         int curSum=0;
  14.         for(int j=0;j<=i;j++){
  15.             if(j==0){
  16.                 curSum=minPathSum.get(i-1).get(0);
  17.             }
  18.             else if(j==i){
  19.                 curSum=minPathSum.get(i-1).get(j-1);
  20.             }else{
  21.                 curSum=Math.min(minPathSum.get(i-1).get(j),minPathSum.get(i-1).get(j-1));
  22.             }
  23.             //之前的值加当前的值
  24.             minPathSum.get(i).add(triangle.get(i).get(j)+curSum);
  25.         }
  26.     }
  27.     int size=triangle.size();
  28.     //值为最后一行第一个
  29.     int allMin=minPathSum.get(size-1).get(0);
  30.     for (int i = 1; i < size; i++) {
  31.         //遍历最后一行找到最小值
  32.         allMin=Math.min(allMin,minPathSum.get(size-1).get(i));
  33.     }
  34.     return allMin;
  35. }

第4题 路径总数(Unique Paths)

2dd830ccd09548008cf046fbc36bac01.png

状态:从(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)

  1. public int uniquePaths (int m, int n) {
  2.        int[][] arr=new int[m][n];
  3.        //初始化
  4.        for(int i=0;i<m;i++){
  5.         arr[i][0]=1;
  6.        }
  7.        for(int i=0;i<n;i++){
  8.         arr[0][i]=1;
  9.        }
  10.        //过程
  11.        for(int i=1;i<m;i++){
  12.         for(int j=1;j<n;j++){
  13.             arr[i][j]=arr[i-1][j]+arr[i][j-1];
  14.         }
  15.        }
  16.        return arr[m-1][n-1];
  17.     }

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

62c0d74a30cb4c5fb3fc716f4dc2636e.png

状态: 从(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)

  1. public int minPathSum (int[][] grid) {
  3.        int n=grid.length;
  4.        int m=grid[0].length;
  5.        if(n==0 || m==0){
  6.         return 0;
  7.        }
  8.        //在grid的基础上改
  9.        for(int i=1;i<n;i++){
  10.         grid[i][0]=grid[i-1][0]+grid[i][0];
  11.        }
  12.        for(int i=1;i<m;i++){
  13.         grid[0][i]=grid[0][i-1]+grid[0][i];
  14.        }
  15.        for(int i=1;i<n;i++){
  16.         for(int j=1;j<m;j++){
  17.             grid[i][j]=Math.min(grid[i-1][j],grid[i][j-1])+grid[i][j];
  18.         }
  19.        }
  20.        return grid[n-1][m-1];
  22.     }

第6题 背包问题

4e32b11b32394685859dfde465185131.png

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

状态转移方程:

1.能放入:

1.不放:和前一个相同

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

2.不能放入:

和前一个相同

初识状态:

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

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

返回结果F(m,n)

  1. public int backPackII(int m, int[] a, int[] v) {
  2.         //得到商品总个数
  3.         //包大小为0,或没有商品直接返回
  4.         //创建二维数组:表示背包总价值   列表示放入的商品个数  行表示包的大小
  5.         //初始化  行为0,或列为0,结果都为0
  6.         //过程  判断商品大小,有放入和不放入两种
  7.         //返回
  8.         int num=a.length;
  9.         if(m==0 || num==0){
  10.             return 0;
  11.         }
  12.           // 0,0返回,所以要+1
  13.         int[][] dp=new int[num+1][m+1];
  14.         for(int i=0;i<=num;i++){
  15.             dp[i][0]=0;
  16.         }
  17.         for(int i=0;i<=m;i++){
  18.             dp[0][i]=0;
  19.         }
  20.       //从1到num开始遍历
  21.         for(int i=1;i<=num;i++){
  22.             for(int j=1;j<=m;j++){
  23.                //a,v数组是从0开始的
  24.                //dp从1开始
  25.                 if(a[i-1]>j){
  26.                     dp[i][j]=dp[i-1][j];
  27.                 }else{
  28.                     int cur=dp[i-1][j-a[i-1]]+v[i-1];
  29.                     dp[i][j]=Math.max(cur,dp[i-1][j]);
  30.                 }
  31.             }
  32.         }
  33.         return dp[num][m];

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

126d677eb9574a9b9163f1af40c03d83.png

如果从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开始 最大分割次数为每一个字母都分割一次

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

  1. import java.util.*;
  4. public class Solution {
  5.     /**
  6.      * 
  7.      * @param s string字符串 
  8.      * @return int整型
  9.      */
  10.  public int minCut (String s) {
  11.     int len=s.length();
  12.     if(len==0){
  13.         return 0;
  14.     }
  15.     int[] minCut=new int[len+1];
  16.     //初始化
  17.     for(int i=0;i<=len;i++){
  18.         minCut[i]=i-1;
  19.     }
  20.     for (int i = 1; i <=len ; i++) {
  21.         for (int j = 0; j <=i ; j++) {
  22.             //前面的循环就直接可以拿到0-j是不是回文串的结果
  23.             //前面的结果是已知的,要判断后面的是不是回文串
  24.             if(isPal(s,j,i-1)){
  25.                 minCut[i]=Math.min(minCut[i],minCut[j]+1);
  26.             }
  27.         }
  28.     }
  29.     return minCut[len];
  31. }
  33. private boolean isPal(String s, int start, int end) {
  34.     while(start<end){
  35.         if(s.charAt(start)!=s.charAt(end)){
  36.             return false;
  37.         }
  38.         start++;
  39.         end--;
  40.     }
  41.     return true;
  42. }
  43. }

第8题 编辑距离(Edit Distance)

57e9495d758b4ebf84b2399cf703f961.png

问题: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.*;

  1. public class Solution {
  2.     /**
  3.      * 
  4.      * @param word1 string字符串 
  5.      * @param word2 string字符串 
  6.      * @return int整型
  7.      */
  8.      public int minDistance (String word1, String word2) {
  9.         // write code here
  10.         if(word1.isEmpty() || word2.isEmpty()){
  11.             return Math.max(word1.length(),word2.length());
  12.         }
  13.         int row=word1.length();
  14.         int col=word2.length();
  15.         int[][] dp=new int[row+1][col+1];
  16.         for(int i=0;i<=row;i++){
  17.             dp[i][0]=i;
  18.         }
  19.         for(int i=0;i<=col;i++){
  20.             dp[0][i]=i;
  21.         }
  22.         for(int i=1;i<=row;i++){
  23.             for(int j=1;j<=col;j++){
  24.                 int cur=Math.min(dp[i-1][j],dp[i][j-1])+1;
  25.                 if(word1.charAt(i-1) ==word2.charAt(j-1)){
  26.                     dp[i][j]=Math.min(dp[i-1][j-1],cur);
  27.                 }else{
  28.                     dp[i][j]=Math.min(dp[i-1][j-1]+1,cur);
  29.                 }
  30.             }
  31.         }
  32.         return dp[row][col];
  33.     }
  34. }

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

832bad95de384675836e6096b1fad994.png

  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.*;

  1. public class Solution {
  2.     /**
  3.      * 
  4.      * @param S string字符串 
  5.      * @param T string字符串 
  6.      * @return int整型
  7.      */
  8.    public int numDistinct (String S, String T) {
  9.         int slen=S.length();
  10.         int tlen=T.length();
  11.         //初始化
  12.         int[][] dp=new int[slen+1][tlen+1];
  13.         dp[0][0]=1;
  14.         for(int i=1;i<=slen;i++){
  15.             dp[i][0]=1;
  16.         }
  17.         for(int i=1;i<=tlen;i++){
  18.             dp[0][i]=0;
  19.         }
  20.         for(int i=1;i<=slen;i++){
  21.             for(int j=1;j<=tlen;j++){
  22.                 if(S.charAt(i-1)==T.charAt(j-1)){
  23.                     dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
  24.                 }else{
  25.                     dp[i][j]=dp[i-1][j];
  26.                 }
  27.             }
  28.         }
  29.         return dp[slen][tlen];
  30.     }
  31. }

发表评论

表情：
评论列表 （有 0 条评论，147人围观）

还没有评论，来说两句吧...

相关阅读

    相关 动态规划（练习题目）

    故事开始以前 最初的那些春天 阳光洒在杨树上 风吹来 闪银光 街道平静而温暖 钟走得好慢 那是我还不识人生之味的年代 我情窦还不开 你的衬衣如雪 盼着杨树叶

    た 入场券た 入场券/ 0 赞/ 68 阅读