当前位置：首页 > article >正文

leedCode - - - 动态规划

article 2024/9/26 1:24:11

1.斐波那契数列（LeetCode 509）

2.零钱兑换（ LeetCode 322 ）

3.爬楼梯（ LeetCode 70 ）

4.不同路径（ LeetCode 62 ）

5.最长递增子序列（LeetCode 300）

6.编辑距离（LeetCode 72）

1.斐波那契数列（LeetCode 509）

https://leetcode.cn/problems/fibonacci-number/description/

使用常规的递归方法，是自上而下，时间复杂度很高（O（2^n））。

class Solution {
    public int fib(int n) {
       if(n==0)return 0;
       if(n==1)return 1;
       return fib(n-1)+fib(n-2); 
    }
}

使用动态规划，对每项斐波那契数进行保存，减少重复的计算过程。是自下而上的一种方式

class Solution {
    public int fib(int n) {
     int[] dp=new int[n+1];
     if ( n < 2) return n;
     dp[0]=0;
     dp[1]=1;
     for(int i=2;i<=n;i++){
        dp[i]=dp[i-1]+dp[i-2];
     }
     return dp[n];
    }
}

2.零钱兑换（ LeetCode 322 ）

https://leetcode.cn/problems/coin-change/

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

class Solution {
    public int coinChange(int[] coins, int amount) {
        int[] dp=new int[amount+1];
        Arrays.fill(dp,-1);
        dp[0]=0;
        for(int i=1;i<=amount;i++){
            for(int j=0;j<coins.length;j++){
                if(coins[j]<=i && dp[i-coins[j]]!=-1){
                    if(dp[i]==-1 || dp[i-coins[j]]+1<dp[i]){
                        dp[i]=dp[i-coins[j]]+1;
                    }
                }
            }
        }
        return dp[amount];
    }
}

class Solution {
    public int coinChange(int[] coins, int amount) {

        // 初始化数组 dp，长度为 amount + 1，因为在 dp 数组中还会存储金额为 0 的情况
        // dp[i] 表示想要凑齐 i 元需要的最少硬币个数
        // dp[0] 表示想要凑齐 0 元需要的最少硬币个数
        // dp[1] 表示想要凑齐 1 元需要的最少硬币个数
        int[] dp = new int[amount + 1];

        // 首先将数组 dp 里面的值都初始化为 -1
        Arrays.fill(dp, -1);

        // 想要凑齐 0 元的最少硬币个数是 0 个
        dp[0] = 0;

        // 依次计算想要凑齐 1 元到 amount 的最少硬币个数是多少
        for(int i = 1 ; i <= amount ; i++){
            // 设置一个变量 j ，遍历数组 coins
            for(int j = 0 ; j < coins.length;j++){
                
                // 1、如果当前的硬币面值 coins[j] 小于了 i，表示这枚硬币有可能可以拼凑到 i
                // 2、那么 i - coins[j] 表示面值 coins[j] 的硬币想要拼凑 i 需要那些面值的硬币金额
                // 3、而 dp[i-coins[j]] 表示想要凑齐 i - coins[j] 元需要的最少硬币个数
                // 4、如果 dp[i-coins[j]] != -1 ，表示想要凑齐 i - coins[j] 元需要的最少硬币个数有结果

                if(coins[j] <= i && dp[i-coins[j]] != -1){
                    // 这个时候，对于金额 i 来说
                    // 1、如果它之前还没有找到凑齐 i 元需要的最少硬币个数
                    // 2、如果此时计算的最少硬币个数比之前保存的结果 dp[i] 更小
                    // 那么更新 dp[i]
                    if(dp[i] == -1 || dp[i-coins[j]] + 1 < dp[i]){
                        // 更新 dp[i]
                        // dp[i] 表示想要凑齐 i 元需要的最少硬币个数
                        // 这个时候 dp[i] 为获取面值为 j 的那 1 个硬币
                        // 加上获取面值为 i - coins[j] 最少需要 dp[i - coins[j]] 个硬币
                        dp[i] = dp[i - coins[j]] + 1;
                    }

                }
            }
        }
        
        // dp[amount] 表示想要凑齐 amount 元需要的最少硬币个数
        return dp[amount];
    }
}

3.爬楼梯（ LeetCode 70 ）

https://leetcode.cn/problems/climbing-stairs/description/

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

class Solution {
    public int climbStairs(int n) {
        //dp[n]存储每一层台阶的爬法数量
        //为了让n=0时不越界，保证dp[1]和dp[2]都有值
        int[] dp=new int[n+2];
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++){
             dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}

4.不同路径（ LeetCode 62 ）

https://leetcode.cn/problems/unique-paths/description/

一个机器人位于一个 m x n 网格的左上角（起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

class Solution {
    public int uniquePaths(int m, int n) {
        int dp[][]=new int[m][n];
        dp[0][0]=1;
        for(int i=0;i<m;i++){
            dp[i][0]=1;
        }
        for(int j=0;j<n;j++){
            dp[0][j]=1;
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

5.最长递增子序列（LeetCode 300）

https://leetcode.cn/problems/longest-increasing-subsequence/description/

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

class Solution {
    public int lengthOfLIS(int[] nums) {
       if (nums.length == 0) return 0;
       int[] dp=new int[nums.length];
       Arrays.fill(dp,1);
       dp[0]=1;
       int max=1;
       for(int i=1;i<nums.length;i++){
        for(int j=0;j<i;j++){
            if(nums[i]>nums[j]){
                dp[i]=Math.max(dp[i],dp[j]+1);
            }
        }
        max=Math.max(max,dp[i]);
       }
       return max;
    }
}

6.编辑距离（LeetCode 72）

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

插入一个字符
删除一个字符
替换一个字符

示例 1：

输入：word1 = "horse", word2 = "ros"
输出：3
解释：
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')

class Solution {
    public int minDistance(String word1, String word2) {
        int m = word1.length();
        int n = word2.length();
        int[][] dp = new int[m + 1][n + 1];

        // 初始化
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j;
        }

        // 填充 dp 表
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);
                }
            }
    }
    return dp[m][n];
  }
}

查看全文

http://www.kler.cn/news/283168.html