动态规划初级篇(上)

2年前 (2022) 程序员胖胖胖虎阿
366 0 0

大家好,我是耀星🌟,欢迎来到动态规划频道📡,如何你是一枚新手的话,建议大家能够先学习🔍动态规划入门篇

目录

        ⌛动态规划题目特点

        👇Example1 (换硬币)

        👇Example2 (跳跃游戏)

        👇Example 3 (解密方法)

        👇Example 4(最长升序子串)

        👇Example 5(调手表)

        🚖坐标型动态规划总结

⌛动态规划题目特点

1.计数

        -有多少种方式走到终点

        -有多少种方式选出k个数的和相同

         ...

2.求最大值最小值

        -求路径的最大最小数字和

        -最长上升子序列长度

        ...

3.求存在性

        -取石子游戏,先手是否必胜 

        -能不能选出k个数和是sum

        ... 

👇Example1 (换硬币)

 你有三种硬币,分别面值2元,5元和7元,每种硬币都有足够多,假设买一本书需要27元,如何用最少的数量的硬币买到这本书,如果给定金额不能够拼出返回-1。

LintCode链接:换硬币

⚖1.确定状态

⏯最后一步:

最后一步我们可能选2元,选择5元,选择7元,如果告诉你拼出25元最少要5枚,拼出22元最少要5枚,拼出20元最少要四枚。那么你最后当然会选择7元作为最后一枚硬币,拼出27元。

🏔子问题:

动态规划初级篇(上)

如果最后一步是选择2元

dp[27] = dp[27-2]+1;//转化为求25元能够用最少硬币拼出

如果最后一步是选择5元

dp[27] = dp[27-5]+1;//转化为求22元能够用最少硬币拼出

如果最后一步是选择7元

dp[27] = dp[20] +1;//转化为求20元能够用最少硬币拼出

我门只是做了假设最后一步应该怎么走,那么具体怎么走才是最优的呢?

dp[27] = min{dp[20],dp[25],dp[22]}+1

 ⚛2.转移方程

动态规划初级篇(上)

 🌎3.初始条件和边界情况

dp[0] = 0;//0元用0枚硬币拼出

如过i-k<0时,则不能够拼出我们想要的数,设不能拼出为+∞。

例如我们想拼出dp[3]动态规划初级篇(上)

🔀 4.计算顺序

dp[0] dp[1] dp[2] dp[3]....dp[n]

动态规划初级篇(上)

说明:题目中并没有给定确定的硬币面值,但是我们同样可以通过推导得出dp[i]=min{dp[i-k1],dp[i-k2],dp[i-k3]...dp[i-kn]}+1 .

public class Solution {
    public int coinChange(int[] coins, int amount) {
    int m = coins.length;
    if(m == 0 || amount == 0){
        return 0;
    }
    
    int[] dp = new int[amount+1];
    
    //初始化
    dp[0] = 0;
    
    for(int i=1; i<=amount; i++){
        dp[i] = Integer.MAX_VALUE;
        
        //有m个不同的硬币
        for(int j=0; j<m; j++){
            if(i >= coins[j] && dp[i-coins[j]] != Integer.MAX_VALUE){//处理边界情况
                dp[i] = Math.min(dp[i-coins[j]]+1,dp[i]);//转移方程
            }
          }
    }
        //拼不出返回-1
        if(dp[amount] == Integer.MAX_VALUE){
            return -1;
        }
        return dp[amount];
    }
}

📝小结

↘最值型动态规划

↘动态规划组成部分

       -1.确定状态

              最后一步(最后一步应该如何选择硬币k)

              子问题(选择最少的硬币,子问题dp[i-coins[j]]

       2.转移方程

              dp[i] = Math.min{dp[i-2],dp[i-5],dp[i-7]}+1;

        3.初始条件和边界情况

             dp[0] = 0;

             不能拼出i,dp[i] = Integer.MAX_VALUE;

👇Example2 (跳跃游戏)

给出一个非负整数数组,你最初定位在数组的第一个位置。数组中的每个元素代表你在那个位置可以跳跃的最大长度。判断你是否能到达数组的最后一个位置。

样例

输入:A=[2,3,1,1,4]

输出:true

LintCode链接:跳跃游戏

⚖1.确定状态

设定一个数组dp[i]表示是否能够跳到第i个位置,能够跳到为true,不能够跳到为false.

⏯最后一步:从数组的第一个位置开始跳,最后一步要求跳到第n-1块石头,设最后一步是从第i块石头跳到n-1

🏔子问题:是否能够跳跃到第i个位置

🍱原问题:是否能够跳到第n-1个位置

想要跳到n-1,第i个位置需要满足的条件有:

dp[i] == true

i+A[i] >= n-1//从第i个位置开始跳,i+A[i]能够跳到的最大位置>=n-1,那么就能跳到第n-1个位置

状态:dp[i]表示能否跳到第i个位置

⌛2.转移方程

用变量j向前枚举

动态规划初级篇(上)

☑3.初始条件和边界情况

起始位置为数组的第一个元素,所以第一个位置一定能够跳到

dp[0] = true 

🔀4.计算顺序 

dp[0] dp[1] dp[2] dp[3]...dp[n-1]

public class Solution {
    public boolean canJump(int[] A) {

        int n = A.length;
        if(n == 0 || A==null){
            return false;
        }

        boolean[] dp = new boolean[n];
        dp[0] = true;

        for(int i=1; i<n;i++){
            dp[i] = false;
            for(int j = i-1;j>=0;j--){
                if(dp[j] == true && j+A[j] >= i){
                    dp[i] = true;
                    break;
                }
            }
        }

        return dp[n-1];
    }
}

👇Example 3 (解密方法)

解密方法:有一段数字序列,将该段数字序列解密成字符串,一共有多少种解密方法。

1-A  2-B 3-C... 26-Z

例如:

12:L或AB

LintCode链接:解密方法

⚖1.确定状态

⏯最后一步:最后一个字符可能由两位数组成,也有可能由一位数组成。

例如:128439516 

动态规划初级篇(上)

将数字序列划分成若干段数字序列

6为最后一个数字,最后一步可以拼成一个F,16作为最后一个数字也可以可以解密为一个P,如果告诉你N-1个数可以拼出的N1种方案,N-2个数可以拼出N2种方案,那么你一定会计算N个数有多少种解密方法。

🐢子问题:求N-1和N-2个数字序列的解密方法

🍱原问题:求N个数字序列的解密方法

状态:前i个数字序列,有dp[i]种解密方法

⚛2.转移方程

动态规划初级篇(上)

☑3.初始条件和边界情况 

初始条件:dp[0] = 1即空串有一种解密方式

边界情况:i == 1,只看最后一个数字

当最后一位是0时,可能由两位数字组成,若两位都为0或两位大于26则不能组成字符串,所以先默认dp[i] = 0,若不满足组成字符条件,则dp[i]就为0。

🔀4.计算顺序

 dp[0] dp[1] dp[2] dp[3] ...dp[n]

public class Solution {
=
    public int numDecodings(String s) {

        char[] ss = s.toCharArray();
        int n = ss.length;

        if(n == 0){
            return 0;
        }

        int[] dp = new int[n+1];
        dp[0] = 1;

        for(int i=1; i<=n; i++){
            
           dp[i] = 0;先初始化为0,可能存在不能组成字符串的情况
            
           //用一个字符作为结尾
           int t1 = ss[i-1]-'0';
           if(t1>0 && t1<=9){//若t == 0,自动选择后两位作为一个字符
               dp[i]+=dp[i-1];
           }
          
           if(i>=2){
               //取出倒数第二位
              int t2 = (ss[i-2]-'0')*10+ss[i-1]-'0';

               if(t2<=26 && t2>=10){//最后两位小于26并且大于等于10才能组成字符
                   dp[i]+=dp[i-2];
               }       
           }

        }

        return dp[n];
    }
}

👇Example 4(最长升序子串)

给定一个整数数组(下标从 0 到 n-1, n 表示整个数组的规模),请找出该数组中的最长上升连续子序列。(最长上升连续子序列可以定义为从右到左或从左到右的序列。)

LintCode链接:最长升序子串

输入:[5, 4, 2, 1, 3]
输出:4
解释:
给定 [5, 4, 2, 1, 3],其最长上升连续子序列(LICS)为 [5, 4, 2, 1],返回 4。

⚖1.确定状态

通过最优策略选择出最长升序子串的长度

⏯最后一步 :如果告诉你以A[i-1]为结尾的升序子串长度为为N1,如果A[i]>A[i-1],那么以A[i]为结尾的升序子串长度为N1+1,如果A[i]<A[i-1],那么以A[i]为结尾的升序子串长度为1。

🐢子问题:只要知道A[i-1]作为升序子串中最后一个元素的最长升序子串的长度。

🍱原问题:求A[i]前的最长升序子串的长度。

状态:使用dp[i]记录以A[i]元素为为结尾的升序子串中最后一个元素的长度。

例如:

动态规划初级篇(上)

⚛2.转移方程 

动态规划初级篇(上)

☑3.初始条件和边界情况

初始条件:

dp[0] = 1

🔀4.计算顺序

dp[0] dp[1] dp[2] dp[3]...dp[n-1] 

public class Solution {
    //计算最长升序子列
    public int MyLongstIncreasingContinuousSubsequence(int[] A){
        int n = A.length;

        if(n == 0 || A == null){
            return 0;
        }

        int[] dp = new int[n];
        //初始化
        dp[0] = 1;
        int max = 1;//记录最长子串

        for(int i=1; i<n;i++){
            dp[i] = 1;//若没有递增默认为1

            if(A[i]>A[i-1]){
                dp[i] = Math.max(1, dp[i-1]+1);
                max = Math.max(dp[i],max);
            }
        }
        return max;
    }
    public int longestIncreasingContinuousSubsequence(int[] A) {

        int ret1 = MyLongstIncreasingContinuousSubsequence(A);
        
        //倒置字符串,计算最长降序子串
        int left = 0;
        int right = A.length-1;
        while(left < right){
            int temp = A[left];
            A[left] = A[right];
            A[right] = temp;
            left++;
            right--;
        }

        int ret2 = MyLongstIncreasingContinuousSubsequence(A);

        int result = Math.max(ret1, ret2);

        return result;
    }
}

👇Example 5(调手表)

小明买了块高端大气上档次的电子手表,他正准备调时间呢。在 M78 星云,时间的计量单位和地球上不同,M78 星云的一个小时有 n分钟。大家都知道,手表只有一个按钮可以把当前的数加一。在调分钟的时候,如果当前显示的数是 0 ,那么按一下按钮就会变成 1,再按一次变成 2 。如果当前的数是 n - 1按一次后会变成 0。作为强迫症患者,小明一定要把手表的时间调对。如果手表上的时间比当前时间多 1,则要按 n - 1 次加一按钮才能调回正确时间。小明想,如果手表可以再添加一个按钮,表示把当前的数加 k 该多好啊......他想知道,如果有了这个+k 按钮,按照最优策略按键,从任意一个分钟数调到另外任意一个分钟数最多要按多少次。

注意,按 +k按钮时,如果加 k 后数字超过 n-1则会对 n 取模。

比如,n=10, k=6 的时候,假设当前时间是 0,连按 2 次 +k+k 按钮,则调为 2。

输入描述

一行两个整数 n, k(0 < k < n <10^5) (0<k<n≤10^5)意义如题。

输出描述

输出一行一个整数,表示按照最优策略按键,从一个时间调到另一个时间最多要按多少次。

OJ链接:调手表

📡1.确定状态

🌎最后一步:

最后一步要调到n-1的位置,可以从n-1-1 || n-1-k || (j*k)%n的位置调到n-1。

🐢子问题:

如果最优策略是从i-1~i

如果最优策略是从i-k~i

如果最优策略是(j*k)%n~i

转化为求调到时间i-1或i-k或(j*k)%n的最优策略

👉原问题:求调第到第n-1分钟的最优策略

🍉状态:dp[i]为调第i分钟,按表的最少次数。

✨2.转移方程

动态规划初级篇(上)

动态规划初级篇(上)

🚲3.初始条件及边界情况

初始条件:

dp[0] = 0

🔀4.计算顺序

dp[0] dp[1] dp[2] dp[3]...dp[n-1] 

import java.util.Scanner;
import java.util.Arrays;

public class Solution {
    public int MinNumberOfTime {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        int k = scan.nextInt();

        int[] dp = new int[n];
        dp[0] = 0;初始化

        for(int i=1;i<n;i++){
          dp[i] = dp[i-1]+1;
      
          if(i-k>=0 && k>1){
            dp[i] = Math.min(dp[i-k]+1,dp[i]);
          }

          for(int j=2;j<dp[i];j++){//寻找可行的j
            
            if((j*k)%n == i){
              dp[i] = Math.min(dp[i],j);
              break;
            }

          }
        }

        排序找到最大数
        Arrays.sort(dp);

        return dp[n-1]
    }
}

🚖坐标型动态规划总结

🎆给定输入为序列或者网格

🎈动态规划状态下标为序列下标i或者坐标(i,j)

--dp[i]表示以i个元素结尾的某种性质

--d[i][j]表示以坐标(i,j)为结尾的性质

💌初始化设置dp[0]或dp[0][0...n]的值

🛑二维空间优化:滚动数组节省空间

水平有限⏰,希望能够对大家有帮助。感谢大家的支持🙆! 

版权声明:程序员胖胖胖虎阿 发表于 2022年9月8日 下午7:24。
转载请注明:动态规划初级篇(上) | 胖虎的工具箱-编程导航

相关文章

暂无评论

暂无评论...