同步操作将从 程序员充电站/LeetCode-Py 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
计数问题:计算满足特定条件下的可行方案数目的问题。
这里的「可行方案数目」指的是某个问题一共有多少种方法。
「计数问题」本身是组合数学中的重要内容,这类问题通常有两种经典的求解方法:
在解决具体问题时,还需要根据题目的具体情况进行分析。一般情况下,我们使用第 $1$ 种方法来解决。这是因为:
所以我们通常使用「动态规划」的方法来解决计数问题。
计数类 DP:一类使用动态规划方法来统计可行方案数目的问题。区别于求解最优解,计数类 DP 需要统计所有满足条件的可行解数量,同时需要满足不重复、不遗漏的条件。
计数类 DP 的核心思想就是:通过动态规划的算法思想,去计算出解决这个问题有多少种方法。一般来说,计数类 DP 只关注方案数目,不关注具体方案情况。
比如,从一个矩阵的左上角走到右下角,每次只能向右走或者向下走,一共有多少条不同路径。注意:这里求解的是有多少条,而不是具体路线的走法。
描述:给定两个整数 $m$ 和 $n$,代表大小为 $m \times n$ 的棋盘, 一个机器人位于棋盘左上角的位置,机器人每次只能向右、或者向下移动一步。
要求:计算出机器人从棋盘左上角到达棋盘右下角一共有多少条不同的路径。
说明:
示例:
输入:m = 3, n = 7
输出:28
输入:m = 3, n = 2
输出:3
解释:
从左上角开始,总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下
按照路径的结尾位置(行位置、列位置组成的二维坐标)进行阶段划分。
定义状态 $dp[i][j]$ 为:从左上角到达位置 $(i, j)$ 的路径数量。
因为我们每次只能向右、或者向下移动一步,因此想要走到 $(i, j)$,只能从 $(i - 1, j)$ 向下走一步走过来;或者从 $(i, j - 1)$ 向右走一步走过来。所以可以写出状态转移方程为:$dp[i][j] = dp[i - 1][j] + dp[i][j - 1]$,此时 $i > 0, j > 0$。
根据状态定义,最终结果为 $dp[m - 1][n - 1]$,即从左上角到达右下角 $(m - 1, n - 1)$ 位置的路径数量为 $dp[m - 1][n - 1]$。
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[0 for _ in range(n)] for _ in range(m)]
for j in range(n):
dp[0][j] = 1
for i in range(m):
dp[i][0] = 1
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]
描述:给定一个正整数 $n$,将其拆分为 $k (k \ge 2)$ 个正整数的和,并使这些整数的乘积最大化。
要求:返回可以获得的最大乘积。
说明:
示例:
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
按照正整数进行划分。
定义状态 $dp[i]$ 表示为:将正整数 $i$ 拆分为至少 $2$ 个正整数的和之后,这些正整数的最大乘积。
当 $i \ge 2$ 时,假设正整数 $i$ 拆分出的第 $1$ 个正整数是 $j(1 \le j < i)$,则有两种方法:
则 $dp[i]$ 取两者中的最大值。即:$dp[i] = max(j \times (i - j), j \times dp[i - j])$。
由于 $1 \le j < i$,需要遍历 $j$ 得到 $dp[i]$ 的最大值,则状态转移方程如下:
$dp[i] = max_{1 \le j < i}\lbrace max(j \times (i - j), j \times dp[i - j]) \rbrace$。
根据我们之前定义的状态,$dp[i]$ 表示为:将正整数 $i$ 拆分为至少 $2$ 个正整数的和之后,这些正整数的最大乘积。则最终结果为 $dp[n]$。
class Solution:
def integerBreak(self, n: int) -> int:
dp = [0 for _ in range(n + 1)]
for i in range(2, n + 1):
for j in range(i):
dp[i] = max(dp[i], (i - j) * j, dp[i - j] * j)
return dp[n]
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。