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

力扣动态规划-30【算法学习day.124】

article 2025/2/19 16:06:44

前言

###我做这类文章一个重要的目的还是记录自己的学习过程，我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

1.零钱兑换

题目链接:322. 零钱兑换 - 力扣（LeetCode）

题面:

代码:

class Solution {
    private int[] coins;
    private int[][] memo;

    public int coinChange(int[] coins, int amount) {
        this.coins = coins;
        int n = coins.length;
        memo = new int[n][amount + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        int ans = dfs(n - 1, amount);
        return ans < Integer.MAX_VALUE / 2 ? ans : -1;
    }

    private int dfs(int i, int c) {
        if (i < 0) {
            return c == 0 ? 0 : Integer.MAX_VALUE / 2;
        }
        if (memo[i][c] != -1) { 
            return memo[i][c];
        }
        if (c < coins[i]) {
            return memo[i][c] = dfs(i - 1, c);
        }
        return memo[i][c] = Math.min(dfs(i - 1, c), dfs(i, c - coins[i])+1);
    }
}