动态规划2:题目

绝地灬酷狼 2024-03-16 09:48 8阅读 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 {
        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) ##

![5ef74c5d312b40eeb24995bcccf103ff.png][]

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) ##

![ea06ba98f0c64df2bed0951dec422da3.png][]

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

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

状态转移方程:

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) ##

![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)

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) ##

![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)

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题 背包问题 ##

![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)

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返回,所以要+1
            int[][] 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) ##

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

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

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) ##

![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.*;
    
    
    public class Solution {
        /**
         * 
         * @param word1 string字符串 
         * @param word2 string字符串 
         * @return int整型
         */
         public int minDistance (String word1, String word2) {
            // write code here
            if(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) ##

![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.*;
    
    
    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];
        }
    }

[023e0787e60d454080346c27af4e41f8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/7348d4b353394d9eab30eae183a28f4a.png
[5ef74c5d312b40eeb24995bcccf103ff.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/aceec53f3100444386d8e923c244cf9e.png
[ea06ba98f0c64df2bed0951dec422da3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/18510783e22e4915a7b9ae6159f5403c.png
[2dd830ccd09548008cf046fbc36bac01.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/ce1be607fb7d4b0880eb85daa15dfdec.png
[62c0d74a30cb4c5fb3fc716f4dc2636e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/5dc3435dedfb406d83eb7b1123285e87.png
[4e32b11b32394685859dfde465185131.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/6386c0710ead479990289c2c6c722fe4.png
[126d677eb9574a9b9163f1af40c03d83.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/89641554306a415a91c79ab4a2fe1731.png
[57e9495d758b4ebf84b2399cf703f961.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/b5be64489d194c9ba494b7e5598a31f2.png
[832bad95de384675836e6096b1fad994.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/9e470161cbbf4e658df0f9a8a4726244.png