• 算法通关村第19关【白银】| 动态规划高频问题

    1.零钱兑换

    思路：

    确定dp：这里是最少硬币的个数，不是种类

    确定递推公式：dp[j] = Math.min(dp[j],dp[j-coins[i]]+1),不要当前硬币dp[j]还是保持以前的组合方法,要当前硬币dp[j-coins[i]]+1

    确定初始化：dp[0]=0,其他的都得初始化最大值

    确定遍历顺序：组合排列都无所谓，保证完全背包从前往后即可

    1. class Solution {
    2.     public int coinChange(int[] coins, int amount) {
    3.         int max = amount + 1;
    4.         int[] dp = new int[amount+1];
    5.         Arrays.fill(dp,max);
    6.         dp[0] = 0;
    7.         for(int i = 1;i1;i++){
    8.             for(int j = 0;j
    9.                 if(coins[j]<=i)
    10.                     dp[i] = Math.min(dp[i],dp[i-coins[j]]+1);
    11.             }
    12.         }
    13.         return dp[amount] >= max?-1:dp[amount];
    14.     }
    15. }

     2.最长连续递增序列

    思路：

    dp:当前最长的递增子序列长度

    递增的时候：dp[i] = dp[i-1]+1

    1. class Solution {
    2.     public int findLengthOfLCIS(int[] nums) {
    3.         int[] dp = new int[nums.length];
    4.         int res = 1;
    5.         for(int i = 0;i
    6.             dp[i] = 1;
    7.         }
    8.         for(int i = 1;i
    9.             if(nums[i]>nums[i-1]){
    10.                 dp[i] = dp[i-1] + 1;
    11.             }
    12.             res = res > dp[i] ? res : dp[i];
    13.         }
    14.         return res;
    15.     }
    16. }

    3.最长递增子序列

    思路：

    确定dp：包含当前数字的最长递增子序列长度

    确定递推公式：dp[i] = Math.max(dp[i],dp[j]+1)，

    确定初始化：dp[i]=1,只包含当前元素长度为1

    确定遍历顺序：后面的dp依赖前面的得出从前往后

    1. class Solution {
    2.     public int lengthOfLIS(int[] nums) {
    3.         int[] dp =new int[nums.length];
    4.         Arrays.fill(dp,1);
    5.         int res = 0;
    6.         for(int i = 0;i
    7.             for(int j = 0;j
    8.                 if(nums[i]>nums[j]){
    9.                     dp[i] = Math.max(dp[i],dp[j]+1);
    10.                 }          
    11.             }
    12.             res = Math.max(res,dp[i]);
    13.         }
    14.         return res;
    15.     }
    16. }

    4.完全平方数

    思路：

    确定dp：当前数字最少组成数量

    确定递推公式：dp[i] = Math.min(dp[i],dp[i-j*j]+1);当前和取j*j之中的最小

    确定初始化：dp[0]=0,dp为max

    确定遍历顺序：后面的dp依赖前面的得出从前往后

    1. class Solution {
    2.     public int numSquares(int n) {
    3.         int[] dp = new int[n+1];
    4.         Arrays.fill(dp,Integer.MAX_VALUE);
    5.         dp[0] = 0;
    6.         for(int i = 1;i<=n;i++){
    7.             for(int j = 1;j*j<=i;j++){
    8.                 dp[i] = Math.min(dp[i],dp[i-j*j]+1);
    9.             }
    10.         }
    11.         return dp[n];
    12.     }
    13. }

    5.跳跃游戏

    思路：

    确定dp：当前能跳的最远距离

    确定递推公式：dp[i] = Math.max(dp[j],j+nums[j]);

    确定初始化：dp[0]=nums[0],dp为0

    确定遍历顺序：后面的dp依赖前面的得出从前往后

    1. class Solution {
    2.     public boolean canJump(int[] nums) {
    3.         int len = nums.length;
    4.         if(len == 1){
    5.             return true;
    6.         }
    7.         int[] dp = new int[len];
    8.         Arrays.fill(dp,0);
    9.         dp[0] = nums[0];
    10.         for(int i = 0;i
    11.             for(int j = 0;j<=i;j++){
    12.                 dp[i] = Math.max(dp[j],j + nums[j]);
    13.             }
    14.             if(i1&&dp[i]<=i)
    15.                 return false;   
    16.         }
    17.         return true;
    18.     }
    19. }

    6.解码方法

    思路：

    确定dp：当前的解码方案数

    确定递推公式：dp[i] = dp[i-1]+dp[i-2]

    •         当 i-1 和 i 为0 或者 i 为0且 i-1 和 i 大于26：不符合条件，返回0
    •         当i为0，则dp[i] = dp[i-2]
    •         当i-1为0或者i-1不为0且i-1 和 i 大于26，则dp[i] = dp[i-1]
    •         其他情况，dp[i] = dp[i-1] + dp[i-2]

    确定初始化：dp[0]=0

    确定遍历顺序：后面的dp依赖前面的得出从前往后

    1. class Solution {
    2.     public int numDecodings(String s) {
    3.         int len = s.length();
    4.         if(s.charAt(0) == '0'){
    5.             return 0;
    6.         }
    7.         if(len == 1){
    8.             return 1;
    9.         }
    10.         int[] dp = new int[len];
    11.         char[] c = s.toCharArray();
    12.         dp[0] = 1;
    13.         if(isAble(c[0],c[1])&&c[1]!='0'){
    14.             dp[1] = 2;
    15.         }else{
    16.             dp[1] = 1;
    17.         }
    18.         if(c[1] == '0'&&!isAble(c[0],c[1])){
    19.             return 0;
    20.         }
    21.         for(int i = 2;i
    22.             if(c[i] == '0' && c[i-1] == '0'|| (c[i] == '0'&&!isAble(c[i-1],c[i]))){
    23.                 return 0;
    24.             }
    25.             if(c[i]=='0'){
    26.                 dp[i] = dp[i-2];
    27.             }else if(c[i-1] == '0'){
    28.                 dp[i] = dp[i-1];
    29.             }else if(isAble(c[i-1],c[i])){
    30.                 dp[i] = dp[i-1] + dp[i-2];
    31.             }else{
    32.                 dp[i] = dp[i-1];
    33.             }
    34.         }
    35.         return dp[len-1];
    36.     }
    37.  
    38.     public boolean isAble(char c1,char c2){
    39.         int num1 = c1 - '0';
    40.         if(num1 == 0) return false;
    41.         int num2 = c2 - '0';
    42.         int num = num1*10 + num2;
    43.         return num <=26 ? true : false;
    44.     }
    45. }

     也可以判断不符合的条件，更加简洁

    1. class Solution {
    2.     public int numDecodings(String s) {
    3.         int n = s.length();
    4.         int[] f = new int[n + 1];
    5.         f[0] = 1;
    6.         for (int i = 1; i <= n; ++i) {
    7.             if (s.charAt(i - 1) != '0') {
    8.                 f[i] += f[i - 1];
    9.             }
    10.             if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
    11.                 f[i] += f[i - 2];
    12.             }
    13.         }
    14.         return f[n];
    15.     }
    16. }

    7.不同路径II

    思路：

    确定dp：能到达当前位置的路径数

    确定递推公式： dp[i][j] = dp[i-1][j] + dp[i][j-1];

    确定初始化：第一行和第一列为1，注意碰到障碍物后面全是0

    确定遍历顺序：后面的dp依赖前面的得出从前往后，从左往右

    1. class Solution {
    2.     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    3.         int[][] dp = new int[obstacleGrid.length][obstacleGrid[0].length];
    4.         for(int i = 0;i0].length;i++){
    5.             if(obstacleGrid[0][i] == 1){
    6.                 break;
    7.             }
    8.             dp[0][i] = 1;
    9.         }
    10.         for(int i = 0;i
    11.             if(obstacleGrid[i][0] == 1){
    12.                 break;
    13.             }
    14.             dp[i][0] = 1;
    15.         }
    16.         for(int i = 1;i
    17.             for(int j = 1;j0].length;j++){
    18.                 if(obstacleGrid[i][j] != 1){
    19.                     dp[i][j] = dp[i-1][j] + dp[i][j-1];
    20.                 }
    21.             }
    22.         } 
    23.         return dp[obstacleGrid.length-1][obstacleGrid[0].length-1];
    24.     }
    25. }

    8.滚动数组技巧

    思路：

    杨辉三角，除了0号位置和i==j的位置是1，其他都是左上角+右上角的值

    一般解法：二维数组就是初始化一个dp[i][j]，然后逐行遍历相加，输出指定行的值

    现在要进行空间优化O（rowIndex）

    如果我们使用一个一维数组dp[]：

            从前往后遍历相加：121=>131=>1341 会发现原先的2被覆盖替换为了3，导致后面的数计算错误。这时我们可以使用第二个一维数组来帮助我们记录值

    1. class Solution {
    2.     public List getRow(int rowIndex) {
    3.         List pre = new ArrayList();
    4.         for (int i = 0; i <= rowIndex; ++i) {
    5.             List cur = new ArrayList();
    6.             for (int j = 0; j <= i; ++j) {
    7.                 if (j == 0 || j == i) {
    8.                     cur.add(1);
    9.                 } else {
    10.                     cur.add(pre.get(j - 1) + pre.get(j));
    11.                 }
    12.             }
    13.             pre = cur;
    14.         }
    15.         return pre;
    16.     }
    17. }

            从后往前遍历：121=>31=>331=>1331 会发现左上角和右上角的值并没被覆盖√

    1. class Solution {
    2.     public List getRow(int rowIndex) {
    3.         List row = new ArrayList();
    4.         row.add(1);
    5.         for (int i = 1; i <= rowIndex; ++i) {
    6.             row.add(0);
    7.             for (int j = i; j > 0; --j) {
    8.                 row.set(j, row.get(j) + row.get(j - 1));
    9.             }
    10.         }
    11.         return row;
    12.     }
    13. }

  • 相关阅读:
    使用Jmeter+ant进行接口自动化测试(数据驱动)
    数据结构-红黑树
    【Linux】多路IO复用技术②——poll详解&如何使用poll模型实现简易的一对多服务器（附图解与代码实现）
    K8S部署Dashboard
    基于物联网的教室人数检测系统-设计说明书
    【Vue3.0】watch监听事件
    2022年，有哪些适合普通人的风口项目？
    运维实战100：CDH5.16.2升级至CDH6.3.2
    【算法训练营】 - ①① 暴力递归
    JAVA:实现是否为Prime素数算法(附完整源码)
  • 原文地址：https://blog.csdn.net/Candy___i/article/details/133916368