动态规划的思想_大事化小小事化了体现出的问题求解思想是

作者：不正经 | 2024-04-12 22:42:35

踩

大事化小小事化了体现出的问题求解思想是

动态规划：通俗一点说就是大事化小，小事化无的思想。其在处理问题时候，会将小问题的结果保存起来，供大问题求解的时候使用。
1、 动态规划的三个特点

把原来的问题分解成几个相似的子问题
所有的子问题只需要解决一次
求解的过程中，需要保存子问题的解

2、动态规划的本质：是对问题状态的定义和状态转移方程的定义（一个状态---->l另外一个状态的）

3、动态规划问题从以下四个角度考虑

状态定义
状态转移方程的定义
状态的初始化(值是确定的）
返回结果

应用场景：最大值、最小值、判断方法是否可行，方案个数等

经典面试题1
题目描述： 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39

状态定义：F(n),第n项的值
状态转移方程的定义：F(n)=F(n-1)+F(n-2)
状态的初始化:F(1)=F(2)=1
返回结果:F(n)

public class Solution {
    public int Fibonacci(int n) {
            if(n==0){
            return 0;
        }
        if(n==1||n==2){
            return 1;
        }
        //F(1)
        int a=1;
        //F(2)
        int b=1;
        int sum=0;
        for(int i=3;i<=n;i++){
            //F(n)=F(n-1)+F(n-2)
            sum=a+b;
            a=b;
            b=sum;
        }
        return sum;
    
}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

经典面试题2
题目描述： 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多
少种跳法。

状态定义：F(n),跳法第n次跳上台阶的
状态转移方程的定义：
最后一步跳一级：则有F(n-1)方法
最后一步跳两级：则有F(n-2)方法
…
最后一步跳n-1级：则有F(1)方法
因此：
F(n)=F(n-1)+F(n-2)+F(n-3)+…+F(1)
F(n-1)=F(n-2)+F(n-3)+…+F(1)
F(n)=2*F(n-1)
状态的初始化:F(1)=1
返回结果:F(n)

 public class Solution {
    public int JumpFloorII(int target) {
            if(target<=0){
            return 0;
        }
        //初始状态
        if(target=1){
            return 1;
        }
        int sum=1;
       /*for(int i=2;i<=n;i++){
            //F(n)=2*F(n-1）
            sum*=2;
        }*/
        //降低时间复杂度
        sum=1<<(n-1);
        return sum;
        return sum;
    
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

经典面试题3
题目描述： 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
n<=39

状态定义：F(n),第n项的值
状态转移方程的定义：F(n)=F(n-1)+F(n-2)
状态的初始化:F(0)=0 F(1)=1
返回结果:F(n)

public class Solution {
    public int JumpFloor(int target) {
       if(target<=0){
          return 0;
      }
      if(target<=3){
          return target;
        }
        int temp1=2;
        int temp2=3;
        int sum=0;
        for(int i=4;i<=target;i++){
            sum=temp1+temp2;
            temp1=temp2;
            temp2=sum;
        }
        return sum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

经典面试题4
**题目描述：**我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？。
n<=39
跟青蛙只能跳一次和两次台阶一样

状态定义：F(n),第n项的方法,
状态转移方程的定义：F(n)=F(n-1)+F(n-2)
状态的初始化:F(0)=0 F(1)=1
返回结果:F(n)

public class Solution {
    public int RectCover(int target) {
       if(target<=0){
           return 0;
       }
        if(target<=2){
            return target;
        } 
        int a=1;
        int b=2;
        int sum=0;
        for(int i=3;i<=target;i++){
          sum=a+b;
            a=b;
            b=sum;
        }
        return sum;
    }
    
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

经典面试题5
题目描述： HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

状态定义：F(i),截止到i，最大子数列F[i],
状态转移方程的定义：
F(i): max(F(i-1)+a[i],a[i])
F(1):6
F(2): -3 , -3+6, max(F(1)+a[i],a[i]
F(3):-2,-2±3,-2±3+6,max(F(2)+a[i],a[i]
状态的初始化:F(0)=a[0]
返回结果:返回最大的子数列 max(F[i])

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
         int[] ret=new int[array.length];
        //找截止到i的最大子序列
        ret[0]=array[0];
        for(int i=1;i<array.length;i++){
            ret[i]=Math.max(ret[i-1]+array[i],array[i]);
        }
        //在所有子序列里面找到最大的
        int maxNum=ret[0];
        for(int i=1;i<ret.length;i++){
            maxNum=Math.max(maxNum,ret[i]);
        }
        return maxNum;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

经典面试题7
题目描述： 给定字符串s和单词字典dict，确定s是否可以被分割成一个或多个字典单词的空格分隔序列。

例如，给定
s =“leetcode”，
dict = [“leet”，“code”]。

返回true，因为“leetcode”可以被分段为“leet code”。

状态定义：F(i),前i个字符能否被分割,
状态转移方程的定义：(j<i)&&(F(j)&&(j+1~i)能否被分割
状态的初始化:F(0)=true
返回结果:F(n)

public class Solution {
    public boolean wordBreak(String s, Set<String> dict) {
        if(s.isEmpty()){
            return false;
        }
        if(dict.isEmpty()){
            return false;
        }
        Iterator<String> iterator=dict.iterator();
        //得到字典单词的最大长度
        int maxLength=0;
        while (iterator.hasNext()){
            int length=iterator.next().length();
            if(length>maxLength){
                maxLength=length;
            }
        }
        //用来储存，前j是否可以分割,注意边界为s.length()+1
        boolean [] booleans=new boolean[s.length()+1];
        //" "
        booleans[0]=true;
        for(int i=1;i<=s.length();i++){
            for (int j=i-1;j>=0;j--){
                //如果子串大于字典最大的单词长度，跳过
                if((i-j)>maxLength){
                    break;
                }
                //(F(j)&&(j+1~i)能否被分割
                if(booleans[j]&&dict.contains(s.substring(j,i))){
                    booleans[i]=true;
                    break;
                }
            }
        }
        return booleans[s.length()];
    }
}    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

经典面试题8
题目描述：
给定一个三角形，找到从上到下的最小路径总和。您可以移动到下面一行中相邻数字的每一步。

例如，给定以下三角形

[
[ 2 ]，
[ 3,4 ]，
[6，5，7]，
[4，1，8,3]
]

从上到下的最小路径总和为11（即，2 + 3 + 5 + 1 = 11）。

注意：
如果只能使用O（n）额外空间来执行此操作，则可以使用额外点，其中n是三角形中的总行数
方法1：

状态定义：子状态：从(0,0)到(1,0),(1,1),(2,0),…(n,n)的最短路径和
F(i,j): 从(0,0)到(i,j)的最短路径和
F(i,j) = min( F(i-1, j-1), F(i-1, j)) + triangle[i][j]
状态的初始化:F(0,0) = triangle[0][0]
返回结果:min(F(n-1, i))

import java.util.ArrayList;
public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
       if(triangle.isEmpty()){
           return 0;
       }
        int[][] dp=new int[triangle.size()+1][triangle.size()+1];
        //初始状态
        dp[0][0]=triangle.get(0).get(0);
       for(int i=1;i<triangle.size();i++){
           for(int j=0;j<=i;j++){
               //处理边界
               if(j==0){
                 dp[i][j]=dp[i-1][j];
               }else if (j==i){
                  dp[i][j]=dp[i-1][j-1];
               }
               else {
                   dp[i][j]=Math.min(dp[i-1][j],dp[i-1][j-1]);
               }
               //F(i,j) = min( F(i-1, j-1), F(i-1, j)) + triangle[i][j]
               dp[i][j]=dp[i][j]+triangle.get(i).get(j);
           }
       }
       //到达最后一行元素，查看谁的数值最小
       int result=dp[triangle.size()-1][0];
       for(int i=1;i<triangle.size();i++){
           result=Math.min(dp[triangle.size()-1][i],result);
       }
       return result;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

方法2：

状态定义：
子状态：从(n,n),(n,n-1),…(1,0),(1,1),(0,0)到最后一行的最短路径和
F(i,j): 从(i,j)到最后一行的最短路径和
状态转移方程的定义：min( F(i+1, j), F(i+1, j+1)) + triangle[i][j]
状态的初始化:F(n-1,0) = triangle[n-1][0], F(n-1,1) = triangle[n-1][1],…, F(n-1,n-1) = triangle[n-1][n-1]
返回结果:F(0, 0)

import java.util.ArrayList;
public class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
       int length=triangle.size();
        int[][] dp=new int[length+1][length+1];
        //获取最后一行元素
        for(int j=0;j<length;j++){
            dp[length-1][j]=triangle.get(length-1).get(j);
        }
        //从倒数第二行开始
        for(int i=length-2;i>=0;i--){
            for(int j=0;j<=i;j++){
            //F(i,j) = min( F(i+1, j), F(i+1, j+1)) + triangle[i][j]
                dp[i][j]=Math.min(dp[i+1][j],dp[i+1][j+1])+triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

经典面试题9
题目描述：
在一个m*n的网格的左上角有一个机器人，机器人在任何时候只能向下或者向右移动，
机器人试图到达网格的右下角，有多少可能的路径。
在这里插入图片描述

1）状态的定义：
从左上角到（i，j)路径总数
2）状态的转移方程:
F(i,j)=F(i-1,j)+F（i，j-1）
3）状态的初始化（值确定的）
Ｆ（０，０）＝１　＝Ｆ（ｉ，０）＝Ｆ（０，ｊ）　　　　　　　
第一行，第一列也是１
4）返回的结果
return PathNum[n-1][m-1]

public class Solution {
    public int uniquePaths(int m, int n) {
 if(n<0||m<0){
            return 0;
        }
       int [][] array=new int[m][n];
          //初始化，第一行，第一列都为1
        for(int i=0;i<m;i++){
            array[i][0]=1;
        }
        for(int j=0;j<n;j++){
            array[0][j]=1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                array[i][j]=array[i-1][j]+array[i][j-1];
            }
        }
        return array[m-1][n-1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/413057