不同路径-Leetcode 62

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

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

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

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3
输出：28

示例 4：

输入：m = 3, n = 3
输出：6

public int uniquePaths(int m, int n) {
    // 创建一个二维数组 dp 来存储子问题的解
    int[][] dp = new int[m][n];

    // 初始化第一列的所有单元格为 1，因为从起点到达这些位置只有一种方式（一直向下）
    for (int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }

    // 初始化第一行的所有单元格为 1，因为从起点到达这些位置只有一种方式（一直向右）
    for (int j = 0; j < n; j++) {
        dp[0][j] = 1;
    }

    // 动态规划填充 dp 数组
    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];
}

0-1 背包问题

n个物品都是固体，有重量和价值，现在你要取走不超过 10克 的物品，每次可以不拿或全拿，问最高价值是多少

public class Knapsack {

    static class Item {
        int index;
        String name;
        int weight;
        int value;

        public Item(int index, String name, int weight, int value) {
            this.index = index;
            this.name = name;
            this.weight = weight;
            this.value = value;
        }

        @Override
        public String toString() {
            return "Item(" + name + ")";
        }
    }

    public static void main(String[] args) {
        // 定义物品数组
        Item[] items = new Item[]{
                new Item(1, "黄金", 4, 1600),
                new Item(2, "宝石", 8, 2400),
                new Item(3, "白银", 5, 30),
                new Item(4, "钻石", 1, 10_000),
        };

        // 调用选择函数，背包总容量为10
        System.out.println(select(items, 10));
    }

    /**
     * 使用动态规划解决0/1背包问题。
     *
     * @param items 物品数组
     * @param total 背包总容量
     * @return 最大价值
     */
    static int select(Item[] items, int total) {
        // 创建二维数组 dp 来存储子问题的解
        int[][] dp = new int[items.length][total + 1];

        // 初始化第一行：只考虑第一个物品的情况
        Item item0 = items[0];
        for (int j = 0; j < total + 1; j++) {
            if (j >= item0.weight) {
                dp[0][j] = item0.value;
            }
        }

        // 动态规划填充 dp 数组
        for (int i = 1; i < dp.length; i++) {
            Item item = items[i];
            for (int j = 0; j < total + 1; j++) {
                // x: 上一次同容量背包的最大价值
                int x = dp[i - 1][j];
                if (j >= item.weight) {
                    // y: 剩余背包空间能装下的最大价值 + 这次物品价值
                    int y = dp[i - 1][j - item.weight] + item.value;
                    dp[i][j] = Integer.max(x, y);
                } else {
                    dp[i][j] = x;
                }
            }
        }

        // 返回右下角单元格的值，即为从起点到终点的最大价值
        return dp[dp.length - 1][total];
    }

    /**
     * 打印二维数组 dp 的内容。
     *
     * @param dp 二维数组
     */
    static void print(int[][] dp) {
        for (int[] row : dp) {
            for (int cell : row) {
                System.out.print(cell + "\t");
            }
            System.out.println();
        }
        System.out.println();
    }
}

零钱兑换问题-Leetcode322

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

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

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

示例 1：

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

输入：coins = [2], amount = 3
输出：-1

示例 3：

输入：coins = [1], amount = 0
输出：0

public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[][] dp = new int[coins.length][amount + 1];
        for (int j = 1; j < amount + 1; j++) {
            if (j >= coins[0]) {
                dp[0][j] = 1 + dp[0][j - coins[0]];
            } else {
                dp[0][j] = max;
            }
        }

        for (int i = 1; i < coins.length; i++) {
            for (int j = 1; j < amount + 1; j++) {
                if (j >= coins[i]) {
                    dp[i][j] = Math.min(dp[i - 1][j], 1 + dp[i][j - coins[i]]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
            print(dp);
        }
        int r = dp[coins.length - 1][amount];
        return r > amount ? -1 : r;
    }

零钱兑换 II-Leetcode 518

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

请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

假设每一种面额的硬币有无限个。 

题目数据保证结果符合 32 位带符号整数。

示例 1：

输入：amount = 5, coins = [1, 2, 5]
输出：4
解释：有四种方式可以凑成总金额：
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2：

输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。

示例 3：

输入：amount = 10, coins = [10] 
输出：1

class Solution {
   public int change(int amount, int[] coins) {
       int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int j = coin; j < amount + 1; j++) {
                dp[j] = dp[j] + dp[j - coin];
            }
        }
        return dp[amount];
}
}