带你读《图解算法小抄》二十一、动态规划（5）

带你读《图解算法小抄》二十一、动态规划（4）https://developer.aliyun.com/article/1347961?groupCode=tech_library

8.不同路径

1）题目描述

一个机器人位于一个 m x n 的网格的左上角。机器人每次只能向下或向右移动一步。机器人试图达到网格的右下角。问总共有多少条不同的路径可以到达终点？

2）解题步骤

为了计算到达终点的不同路径数，我们可以使用动态规划的思想来解决问题。

• 定义状态：我们可以将问题转化为到达每个格子的不同路径数。令 dp[i][j] 表示到达网格第 i 行、第 j 列的格子的不同路径数。
  
• 初始状态：根据题目的约束，机器人只能向下或向右移动，因此对于第一行和第一列的格子，机器人只能沿着一条路径到达。即 dp[i][0] = 1，dp[0][j] = 1。
  
• 状态转移方程：对于其他格子，到达当前格子的不同路径数等于到达其上方格子的路径数加上到达其左方格子的路径数。因此，状态转移方程为 dp[i][j] = dp[i-1][j] + dp[i][j-1]。
  
• 最终解：问题的解即为到达终点的不同路径数，即 dp[m-1][n-1]，其中 m 是网格的行数，n 是网格的列数。
  

下面是使用动态规划解决不同路径问题的算法框架：

function uniquePaths(m, n) {
  const dp = new Array(m);
  for (let i = 0; i < m; i++) {
    dp[i] = new Array(n).fill(0);
  }  for (let i = 0; i < m; i++) {
    dp[i][0] = 1;
  }  for (let j = 0; j < n; j++) {
    dp[0][j] = 1;
  }  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
    }
  }
  return dp[m - 1][n - 1];
}

9.零钱兑换

1）题目描述

给定不同面额的硬币 coins 和一个总金额 amount，编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能够凑出总金额，返回 -1。

2）解题步骤

为了计算凑成总金额的最少硬币个数，我们可以使用动态规划的思想来解决问题。

• 定义状态：我们可以将问题转化为凑出每个金额所需的最少硬币个数。令 dp[i] 表示凑出金额 i 所需的最少硬币个数。
  
• 初始状态：根据题目的约束，凑出金额为 0 的最少硬币个数为 0。即 dp[0] = 0。
  
• 状态转移方程：对于金额 i，我们可以选择任意一种面额的硬币 coin，并从 i-coin 的金额中选择最少硬币个数，然后再加上一枚硬币 coin。因此，状态转移方程为 dp[i] = min(dp[i - coin] + 1)，其中 coin 取遍所有硬币的面额。
  
• 最终解：问题的解即为凑出总金额所需的最少硬币个数，即 dp[amount]。
  

下面是使用动态规划解决零钱兑换问题的算法框架：

function coinChange(coins, amount) {
  const dp = new Array(amount + 1).fill(Infinity);
  dp[0] = 0;  for (let i = 1; i <= amount; i++) {
    for (const coin of coins) {
      if (i - coin >= 0) {
        dp[i] = Math.min(dp[i], dp[i - coin] + 1);
      }
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

带你读《图解算法小抄》二十一、动态规划（6）https://developer.aliyun.com/article/1347957?groupCode=tech_library