题解 | #倒水#

解题思路

这是一个递归/动态规划问题，需要计算将 升水倒入 个相同容器的不同倒法数量：

1. 每个容器容量足够大
2. 允许容器为空
3. 相同的倒水数量序列视为同一种倒法

解题思路：

1. 当 或 ，或 时，只有一种倒法
2. 对于其他情况，可以分为 个容器装水的情况
3. 使用动态规划避免重复计算

代码

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int countWays(int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        
        // 初始化边界条件
        for (int i = 0; i <= m; i++) {
            dp[i][1] = 1;  // 只有一个容器
        }
        for (int j = 1; j <= n; j++) {
            dp[0][j] = 1;  // 没有水
            dp[1][j] = 1;  // 只有1升水
        }
        
        // 动态规划
        for (int i = 2; i <= m; i++) {
            for (int j = 2; j <= n; j++) {
                int temp = min(i, j);
                for (int k = 1; k <= temp; k++) {
                    if (k == 1) {
                        dp[i][j] += dp[i][k];
                    } else {
                        dp[i][j] += dp[i-k][k];
                    }
                }
            }
        }
        
        return dp[m][n];
    }
};

int main() {
    int x;
    cin >> x;
    Solution sol;
    while (x--) {
        int m, n;
        cin >> m >> n;
        cout << sol.countWays(m, n) << endl;
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static int countWays(int m, int n) {
        int[][] dp = new int[m + 1][n + 1];
        
        // 初始化边界条件
        for (int i = 0; i <= m; i++) {
            dp[i][1] = 1;  // 只有一个容器
        }
        for (int j = 1; j <= n; j++) {
            dp[0][j] = 1;  // 没有水
            dp[1][j] = 1;  // 只有1升水
        }
        
        // 动态规划
        for (int i = 2; i <= m; i++) {
            for (int j = 2; j <= n; j++) {
                int temp = Math.min(i, j);
                for (int k = 1; k <= temp; k++) {
                    if (k == 1) {
                        dp[i][j] += dp[i][k];
                    } else {
                        dp[i][j] += dp[i-k][k];
                    }
                }
            }
        }
        
        return dp[m][n];
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        while (x-- > 0) {
            int m = sc.nextInt();
            int n = sc.nextInt();
            System.out.println(countWays(m, n));
        }
        sc.close();
    }
}

def count_ways(m: int, n: int) -> int:
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 初始化边界条件
    for i in range(m + 1):
        dp[i][1] = 1  # 只有一个容器
    for j in range(1, n + 1):
        dp[0][j] = 1  # 没有水
        dp[1][j] = 1  # 只有1升水
    
    # 动态规划
    for i in range(2, m + 1):
        for j in range(2, n + 1):
            temp = min(i, j)
            for k in range(1, temp + 1):
                if k == 1:
                    dp[i][j] += dp[i][k]
                else:
                    dp[i][j] += dp[i-k][k]
    
    return dp[m][n]

# 读取输入
x = int(input())
for _ in range(x):
    m, n = map(int, input().split())
    print(count_ways(m, n))

算法及复杂度

• 算法：动态规划
• 时间复杂度：，其中 是水的升数， 是容器数
• 空间复杂度：，用于存储 数组