动态规划（Dynamic Programming）例题步骤详解

文章目录

动态规划（Dynamic Programming）浅学 - 学习笔记
- 题目特点：
- 1、选择硬币组合问题：（Coin Change）
- 动态规划题四个核心步骤：
- - 一、确定状态
  - 二、转移方程
  - 三、初始条件和边界情况
  - 四、计算顺序
  - 小结：
  - 编程代码：（Java）
- 2、多少种路径问题（Unique Paths）
- - 1、确定状态
  - 2、转移方程
  - 3、初始条件和边界情况
  - 4、计算顺序
  - 编程代码：（Java）
- 3、Jump Game
- - 1、确定状态
  - 2、转移方程
  - 3、初始条件和边界情况
  - 4、计算顺序
  - 编程代码：（Java）
  - 总结

动态规划（Dynamic Programming）浅学 - 学习笔记

题目特点：

在这里插入图片描述

1、选择硬币组合问题：（Coin Change）

在这里插入图片描述

动态规划题四个核心步骤：

一、确定状态

在这里插入图片描述

其中，最后一步是指：（上面例子举例说）

在这里插入图片描述

其中，子问题是指：（上面例子举例说）

在这里插入图片描述

递归解法：

在这里插入图片描述

递归解法的问题：

在这里插入图片描述

重复计算，效率不高！

应当如何避免？

将计算结果保存下来（memories），并改变计算顺序。

二、转移方程

在这里插入图片描述

三、初始条件和边界情况

在这里插入图片描述

四、计算顺序

在这里插入图片描述

小结：

在这里插入图片描述

编程代码：（Java）

public class Solution{ 
                      //{2,5,7} 27
  public int coinChange(int A[],int M){ 
    int[] f = new int[M+1]; //0...M
    int len = A.length;
    //初始化
    f[0] = 0;
    int i,j;
    for(i=1;i<=M;++i){ 
      f[1] = Integer.MAX_VALUE;
      //f[i] = min{f[i-A[0]]+1,...,f[i-A[len-1]]+1}
      for(j=0;j<len;++j){ 
        if(i>=A[j] && f[i-A[j]] != Integer.MAX_VALUE){  //判断条件
          f[i] = Math.min(f[i-A[j]]+1,f[i]);
        }
      }
    }
    if(f[M] == Math.MAX_VALUE){ 
      f[M] = -1;
    }
    return f[M];
  }
}

2、多少种路径问题（Unique Paths）

在这里插入图片描述

1、确定状态

在这里插入图片描述

子问题：

在这里插入图片描述

2、转移方程

在这里插入图片描述

3、初始条件和边界情况

在这里插入图片描述

4、计算顺序

在这里插入图片描述

编程代码：（Java）

public class Solution{ 
  public int uniquePaths(int m,int n){ 
    int[][] f = new int[m][n];
    int i,j;
    for(i=0;i<m;++i){  //行 从上到下
      for(j=0;j<n;++j){  //列 从左到右
        if(i=0 && j=0){ 
          f[i][j] = 1;
        }else{ 
          f[i][j] = f[i-1][j]+f[i][j-1];
        }
      }
    }
    return f[m-1][n-1];
  }
}

3、Jump Game

在这里插入图片描述

1、确定状态

在这里插入图片描述

子问题：

在这里插入图片描述

2、转移方程

在这里插入图片描述

3、初始条件和边界情况

在这里插入图片描述

4、计算顺序

在这里插入图片描述

编程代码：（Java）

public class Solution{ 
  public boolean canJump(int[] A){ 
    int n = A.length;
    boolean[] f = new boolean[n];
    //初始化
    f[0] = true;
    int i,j;
    for(j = 1;j < n;j++){ 
      f[j] = false;
      for(i=0;i<j;i++){ 
        if(f[i] && i+A[i] >= j){ 
          f[j] = true;
          break;
        }
      }
    }
    return f[n-1];
  }
}

此题若用贪心算法时间复杂度则为O(n):

贪心算法解题思路

这个问题可以通过递归很容易解决来处理，我们想要知道能否到达index，那么只需要知道index之前的元素是不是有nums[i]+i >= index for i in range(index)（也就是index之前是不是有位置可以到达index）。

public class Solution { 
    public boolean canJump(int[] nums) { 
        int reach = nums[0];
        for(int i = 1; i < nums.length && reach >= i; i++)
            if(i + nums[i] > reach) reach = i + nums[i];  //贪心策略
        return reach >= (nums.length-1) ? true : false;
    }
}