从暴力递归到动态规划（二）

整理一篇和递归、动态规划有关的文章

动态规划

  • 动态规划相比暴力递归最明显的就是：以空间换时间
  • 从递归到动态规划：对于可变参数新建空间存储

题目1

  • 题目描述：假设有排成一行的N个位置，记为1~N，开始时机器人在M位置，机器人可以往左或者往右走，如果机器人在1位置，那么下一步机器人只能走到2位置，如果机器人在N位置，那么下一步机器人只能走到N-1位置。规定机器人只能走k步，最终能来到P位置的方法有多少种？

  • 递归解法：写一个方法，形参分别为N、cur（目前位置）、rest（剩余步数）、p（目标位置），递归调用该方法，返回最终步数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    public static int walk(int N,int cur,int rest,int P){
        if(rest==0)
            return cur==p?1:0;
        if(cur==1)
            return walk(N,2,rest-1,P);
        if(cur==N)
            return walk(N,N-1,rest-1,P);
        return walk(N,cur+1,rest-1,P)+walk(N，cur-1，rest-1，P)；
    }

  • 每次调用函数N、P一定，cur和rest不断变化。可以看到，当重复调用f(cur,rest)时，递归解法存在重复计算。故用二维数组存储之。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    public static int walk(int N,int cur,int rest,int p){
        if (N < 2 || rest < 1 || start < 1 || start > N || end < 1 || end > N) {//剪枝
                return 0;
            }
            int[][] dp = new int[N + 1][rest + 1];//每次调用改变当前位置和剩余步数，因此新建二维数组
            dp[end][0] = 1;
            for (int col = 1; col <= rest; col++) {
                dp[1][col] = dp[2][col - 1];
                dp[N][col] = dp[N - 1][col - 1];
                for (int row = 2; row < N; row++) {
                    dp[row][col] = dp[row - 1][col - 1] + dp[row + 1][col - 1];
                }
            }
            return dp[start][rest];
    }

题目2

  • 规定1和A对应，2和B对应……给定一个只有数字组成的字符串，返回有多少种转化结果

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    public static int number(String s){
        if(s==null||s.length()==0)
            return 0;
        char[] str=s.toCharArray();
        int n=str.length;
        int[] dp=new int[n+1];
        dp[n]=1;
        for(int i=n-1;i>=0;i--){
            if(str[i]!='0') {
                dp[i]=dp[i+1];
                if(i==n-1)
                    continue;
                if(str[i]=='1') {
                    dp[i]+=dp[i+2];
                }else if(str[i]=='2') {
                    if(str[i+1]>='0'&&str[i+1]<='6')
                        dp[i]+=dp[i+2];
                }else {
                    dp[i]=dp[i+1];
                }
            }
        }
        return dp[0];
    }

题目3

  • 背包问题：给定两个长度都为N的数组weights和values，分别表示第i号物品重量和价值，给一个正数bag，表示载重bag的袋子，你装的物品不能超过这个袋子，求装下的最大价值.

  • 注：最近在思考一些关于贪心和动态规划的东西。贪心的重点是局部最优，全局最优。但0-1背包问题每次遇到新情况都需要列举所有情况来更新，显然不能用贪心来解。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    public static int getmaxValue(int[] w,int[] v,int bag) {
        if(w.length==0||bag==0)
            return 0;
        int n=w.length;
        int[][] dp=new int[n][bag+1];//前n个物品在容量不同的情况下装载的最大价值
        for(int i=0;i<=bag;i++)
            dp[0][i]=(i>=w[0]?v[0]:0);
        for(int i=1;i<n;i++){
            for(int j=1;j<=bag;j++){
                if(w[i]>j){//装不下
                    dp[i][j]=dp[i-1][j];
                }else{
                    dp[i][j]=Math.max(dp[i-1][j],dp[i][j-w[i]]+v[i]);
                }
            }
        }
        return dp[n-1][bag];
    }

  • 状态压缩：一行空间即可完成该方法

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    public static int getmaxValue(int[] w,int[] v,int bag) {
        if(w.length==0||bag==0)
            return 0;
        int n=w.length;
        int[] dp=new int[bag+1];//前n个物品在容量不同的情况下装载的最大价值
        for(int i=0;i<=bag;i++)
            dp[i]=(i>=w[0]?v[0]:0);
        for(int i=1;i<n;i++){
            for(int j=0;j<=bag;j++) {
                if(j>=w[i]) {
                    dp[j]=dp[j-w[i]]+v[i];
                }
            }
        }
        return dp[bag];
    }

题目4

  • 给定一数组arr，表示不同数值纸牌排成一排，理行人玩家A和B依次拿走每张牌，每次只能拿走两边的牌。玩家A先拿，B后拿。问最后获胜者分数。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    public static int win(int[] arr) {
        if(arr==null || arr.length==0)
            return 0;
        int n=arr.length;
        //每张表有一半空间可用
        int[][] f=new int[n][n];
        int[][] s=new int[n][n];
        for(int i=0;i<n;i++)
            f[i][i]= arr[i];
        //斜方遍历
        for(int i=1;i<n;i++){
            int row=0,col=i;//开始遍历的点
            while(row<n && col<n){
                
                f[row][col]=Math.max(s[row+1][col]+arr[row], s[row][col-1]+arr[col]);
                s[row][col]=Math.min(f[row+1][col], f[row][col-1]);
                
                row++;
                col++;
            }
        }
        return Math.max(f[0][n-1], s[0][n-1]);
    }

题目5

  • leetcode.518 零钱兑换Ⅱ：给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。

  • 本题从一开始的暴力递归逐步分析，到最简的一维数组动态规划。

    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
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    class Solution {
        //递归解
        public int change(int amount, int[] coins) {
            if(coins==null || amount<0)
                return 0;
            return f(coins,0,amount);
        }
        public int f(int[] coins,int i,int rest){//可自由使用由i开始所有面值的硬币任意张，所凑成rest的方法数
            if(i>=coins.length)
                return (rest==0)?1:0;
            int num=0;
            for(int zhang=0;zhang*coins[i]<=rest;zhang++){
                num+=f(coins,i+1,rest-zhang*coins[i]);
            }
            return num;
        }
        
        
        //动态规划解，将参数作最细粒度划分
        public int change(int amount, int[] coins) {
            if(coins==null || amount<0)
                return 0;
            int n=coins.length;
            int[][] dp=new int[n+1][amount+1];//表示：coins[i]之前（不包括i）所有余额情况下的硬币组合数
            dp[0][0]=1;
            for(int i=1;i<=n;i++){//也可从下往上写
                for(int j=0;j<=amount;j++){
                    for(int zhang=0;zhang*coins[i-1]<=j;zhang++)
                        dp[i][j]+=dp[i-1][j-coins[i-1]*zhang];
                }
            }
            return dp[n][amount];
        }
        
        
        //优化解
        public int change(int amount, int[] coins) {
            if(coins==null || amount<0)
                return 0;
            int n=coins.length;
            int[][] dp=new int[n+1][amount+1];//表示：coins[i]之前（不包括i）所有余额情况下的硬币组合数
            dp[0][0]=1;
            for(int i=1;i<=n;i++){//也可从下往上写
                for(int j=0;j<=amount;j++){
                    //区别在于：省去了循环枚举去掉不同张数的情况
                    dp[i][j]=dp[i-1][j];
                    if(coins[i-1]<=j)
                        dp[i][j]+=dp[i][j-coins[i-1]];
                }
            }
            return dp[n][amount];
        }
        
        
        //状态压缩解
        public int change(int amount, int[] coins) {
            if(coins==null || amount<0)
                return 0;
            int n=coins.length;
            int[] dp=new int[amount+1];
            dp[0]=1;
            for(int num:coins){//也可从下往上写
                for(int i=0;i<=amount;i++){
                    if(num<=i)
                        dp[i]+=dp[i-num];
                }
            }
            return dp[amount];
        }
    }

顺便送一个福利

  • leetcode.322 零钱兑换：给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    class Solution {
        public int coinChange(int[] coins, int amount) {
            if(coins==null)
                return -1;
            int n=coins.length;
            int[] dp=new int[amount+1];
            for(int i=1;i<=amount;i++){
                dp[i]=amount+1;//这里的目的在于调整后面求每个金额最小组合个数时产生的错误
                for(int num:coins){
                    if(num<=i){
                        dp[i]=Math.min(dp[i-num]+1,dp[i]);
                    }
                }
            }
            return (dp[amount]==amount+1)?-1:dp[amount];
        }
    }
以上所有代码均为抛砖引玉，仅为入门，要掌握动态规划需要长期练习。
赏

谢谢你请我吃糖果

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

热爱跳舞<br><br>永远是学徒