常用算法之动态规划


前言:

动态规划是十分常用的算法思想,本文针对动态规划的性质、求解例举了几种针对动态规划解法的题目,来解析动态规划解法的思想。

介绍:

动态规划算法通常基于一个递推公式及一个或多个初始状态。当前子问题的解将由上一次子问题的解推出。使用动态规划来解题只需要多项式时间复杂度,因此它比回溯法、暴力法等要快许多。
解决动态规划问题的关键是要找到状态转移方程。将问题分解成最小的子问题,找到由子问题到全局问题的解决方案。

性质:

一般可以采用动态规划求解的问题的一般要具有以下几个性质:

(1) 最优化原理:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构,即满足最优化原理。
(2) 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。
(3) 有重叠子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)。

求解动态规划问题的基本步骤:

(1)分析最优解的性质,并刻画其结构特征。
(2)递归的定义最优解。
(3)以自底向上或自顶向下的记忆化方式(备忘录法)计算出最优值
(4)根据计算最优值时得到的信息,构造问题的最优解

举例:

方格走法

有一个X*Y的网格,某人要在此网格上从左上角到右下角,只能走格点且只能向右或向下走。请设计一个算法,计算该人共有多少种走法。给定两个正整数int x,int y,请返回该人的走法数目。

public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        int[][] array = new int[x+1][y+1];
        array[0][0]=0;
        //生成边界条件
        for (int i = 1; i < x+1; i++) {
            array[i][0]=1;
        }
        for (int i = 1; i < y+1; i++) {
            array[0][i]=1;
        }
        for (int i = 1; i < x+1; i++) {
            for (int j = 1; j < y+1; j++) {
                array[i][j]=array[i-1][j]+array[i][j-1];
            }
        }
        System.out.println(array[x][y]);
    }

分析:例如走到[3,2]这个格子的数目一定是从[3,1]或[2,2]走过来的,那么[3,2]的步数也就是[3,1]和[2,2]之和,所以缩到最小,也就确定了最开始的状态,然后根据这个规律就能计算出[x,y]的步数。

字符串最小变换次数

给定两个字符串,已知可以使用三种方式进行变换

  1. 插入一个字符
  2. 删除一个字符
  3. 更改一个字符
    请设计一个算法,找到两个字符串之间的经历几次最小变换,可以字符串1转换成字符串2
 public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String str1 = "#" + scanner.next();
        String str2 = "#" + scanner.next();
        int[][] dp = new int[str1.length()][str2.length()];

        // 初始化
        for (int i = 1; i < str1.length(); i++)
            dp[i][0] = i;
        for (int i = 1; i < str2.length(); i++)
            dp[0][i] = i;

        for (int i = 1; i < str1.length(); i++) {
            for (int j = 1; j < str2.length(); j++) {
                if (str1.charAt(i) == str2.charAt(j))
                    dp[i][j] = dp[i - 1][j - 1];
                else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1],
                        Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
                }
            }
        }
        System.out.println(dp[str1.length() - 1][str2.length() - 1]);
    }

分析: 可以用dp[i][j]来表示str1在i位置之前和str2在j位置之前字符的最小变换次数,那么dp[i][j]的取值与当前位置字符的判断有关。

递推公式:str1[i] == str2[j]=> dp[i][j] = dp[i-1][j-1]

str1[i] != str2[j]=> dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1

为了初始化方便,可以在str1和str2的首部添加一个哨兵字符

走台阶

每次你可以走 1 或 2 个台阶需要走完n个台阶,有多少走法?

  public static int f(int n){
         if (n==1){
            return 1;
         }else if (n==2){
             return 2;
         }
         return f(n-1)+f(n-2);
     }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(f(n));

    }

分析:第3个台阶其实就是第1个台阶走2步和第2个台阶走1步而来的,所以递推公式就是f(n)=f(n-1)+f(n-2)即可。

  public int FindGreatestSumOfSubArray(int[] array) {
        int max = array[0];
        int res = array[0];
        for (int i = 1; i < array.length; i++) {
            max = Math.max(max + array[i], array[i]);
            res = Math.max(res, max);
        }
        return res;
    }

分析:其实就是这个状态方程 max( dp[ i ] ) = getMax( max( dp[ i -1 ] ) + arr[ i ] ,arr[ i ] )

就是说当累计的max变为负数时,就抛弃。不然这个max哪怕是1,相对于后面单独的累加,其实也是贡献,也就应加上的。

背包问题:

5kg的袋子
物品:物品只有一个,且不能拆分。
钱:6 10 12
Kg:1 2 4

1kg 2kg 3kg 4kg 5kg
加第一个物品 6 6 6 6 6
加第二个物品 6(取上面第一个) 10 16 16 16
加第三个物品 6 10 16 16 18

核心思想:
分解子问题,通过局部最大值得到全局最大。

    //动态规划
    public static void main(String[] args) {
            int value[] = {60,100,120};        //每个物品的钱
            int weight[] = {10,20,40};        //每个物品的重量 和上面的一一对应

            int w = 50;    //袋子的容积
            int n = 3;    //物品的个数
            int dp[][] = new int[n+1][w+1];        //表示分割,成一个 小的表格

            for(int i = 1; i<=n ;i++) {        //表示物品往里面加
                for(int cw = 1; cw <= w; cw ++) {    //袋子在每一个容积下所装的最大的钱
                    if(weight[i - 1] <= cw) {        //表示这个物品可以装
                        dp[i][cw] = Math.max(
                                value[i-1]+dp[i-1][cw-weight[i-1]],        //我装新加的物品
                                dp[i-1][cw]        //我不装这个新加的这个物品
                        );
                    }else {
                        dp[i][cw] = dp[i-1][cw];        //新加的这个装不下 ,那么就取前一个物品装值
                    }
                }
            }
            System.out.println("袋子能装的最大价值:" + dp[n][w]);

    }

分析:我们把5kg袋子拆分成1kg 1kg这样的来计算,每个格子的意思就是当前袋子在这个容量下能装的最大价值。行表示每次加的物品。

第二个进来时,如果此时袋子为2kg,我们知道在第一个物品进来时,2kg最多能装6块钱。,这时候如果我们选择装第二物品那么袋子里面的钱为10块,然后剩余0kg,那么物品1就不能装了。然后发现10块大于袋子里面原来的6快,所以我们选择装第二个 丢掉第一个。
第三个物品进来,如果此时袋子为5kg,我们如果选择加第三个物品,那么袋子容积还剩1kg,能得12块,我们找到上一列1kg袋子的最大价值,为6,所以总的为18.


文章作者: jackey
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 jackey !
评论
  目录