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

力扣动态规划-32【算法学习day.126】

article 2025/2/21 1:50:35

前言

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

习题

1.完全平方数

题目链接:279. 完全平方数 - 力扣（LeetCode）

题面:

代码:

class Solution {
    private static final int[][] memo = new int[101][10001];

    static {
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
    }

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

    public int numSquares(int n) {
        return dfs((int) Math.sqrt(n), n);
    }
}