LeetCode 热题 HOT 100(05,正则表达式匹配) (4)

初始条件和边界情况:初始条件就是f(0),表示的就是0元可以通过0枚硬币组成,而边界情况就是每当面值总额减2、5、7的时候都应该大于0,否则的话无法组成目标面额总值(根据题意自行理解)

计算顺序:要想获得f(x),就必须得到f(x-2)、f(x-5)、f(x-7)的值,也就是除去一枚硬币面额所需要的最少硬币数目

通过如上分析,可以得到如下Java算法;

public int coinChange(int[] coin_list, int coin_value) {
    int[] f = new int[coin_value + 1];
    f[0] = 0;
    for (int i = 1; i <= coin_value; i++) {
        f[i] = Integer.MAX_VALUE;
        for (int j = 0; j < coin_list.length; j++) {
            if (i >= coin_list[j] && f[i - coin_list[j]] != Integer.MAX_VALUE) {
                f[i] = Math.min(f[i], f[i - coin_list[j]] + 1);
            }
        }
    }
    if (f[coin_value] == Integer.MAX_VALUE) { f[coin_value] = -1; }
    return f[coin_value];
}

示例2:在一个矩阵当中,有多少种方式能从左上角走到右下角。(每次行走方向只能往下或往右),比如从(0, 0)出发,有多少种路线走到(4, 5)

时间关系,这里简单分析下。

走到(4, 5)的上一格有两种,一个是(3, 5),另一个是(4, 4),所以走到(4, 5)的路线总数就等于上述两种的总和,对此,我们可以得到如下关系,其中f[i][j]表示的是走到(i, j)的路线种数

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:https://www.heiqu.com/wpjzpg.html