回复李泽瑞の问题

零叁柒

2024-10-10 21:23:13

发布于：浙江

46阅读

0回复

0点赞

你好！

看起来你在实现楼梯走法的动态规划问题时遇到了问题。你的代码大体思路是正确的，即使用字符串来处理大数相加，但在处理进位时可能存在一些问题，特别是在高位进位时。

问题分析

你的 init 函数在进行字符串相加时，处理进位的方式有些问题。当 c1[idx] 达到 10 时，只增加了一次进位，但实际上可能需要多次进位。这会导致最终结果中出现非数字字符，从而输出错误的结果。

例如，当某一位相加后 c1[i] = 10，你只是将 c1[i] 设为 0 并将 c1[i+1] 增加 1，但如果 c1[i+1] 已经是 9，那么 c1[i+1] 变为 10 后就需要继续进位，这在你的代码中没有处理。

解决方案

我们需要确保在所有位的相加过程中，进位被正确处理。可以通过以下几种方式来改进你的代码：

改进进位处理逻辑：在每一位相加后，持续检查是否有进位需要处理，直到没有进位为止。
使用更简洁的字符串逆序相加方法：将字符串逆序后，从低位到高位逐位相加，处理进位。

下面是改进后的代码示例：

#include<bits/stdc++.h>
using namespace std;

typedef string BigInt;

// Function to add two big integers represented as strings
BigInt addStrings(const BigInt &a, const BigInt &b){
    string result = "";
    int carry = 0;
    int n1 = a.size();
    int n2 = b.size();
    int i = n1 - 1;
    int j = n2 - 1;
    
    while(i >=0 || j >=0 || carry){
        int sum = carry;
        if(i >=0){
            sum += a[i] - '0';
            i--;
        }
        if(j >=0){
            sum += b[j] - '0';
            j--;
        }
        carry = sum / 10;
        sum %= 10;
        result += (sum + '0');
    }
    // Reverse the result to get the correct order
    reverse(result.begin(), result.end());
    return result;
}

int main(){
    int n;
    cin >> n;
    // Base cases
    if(n == 1){
        cout << "1";
        return 0;
    }
    if(n == 2){
        cout << "2";
        return 0;
    }
    // Initialize dp array
    vector<BigInt> dp(n+1, "0");
    dp[1] = "1";
    dp[2] = "2";
    for(int i=3; i<=n; i++){
        dp[i] = addStrings(dp[i-1], dp[i-2]);
    }
    cout << dp[n];
    return 0;
}

解释

addStrings 函数：这个函数接收两个字符串形式的大整数，并返回它们的和。通过从字符串的末尾（最低位）开始逐位相加，并处理进位，直到所有位都被处理完毕。
动态规划部分：使用 dp 数组来存储每一步的结果。初始化 dp[1] 为 "1" 和 dp[2] 为 "2"，然后依次计算 dp[i] = dp[i-1] + dp[i-2]。
输出结果：最后输出 dp[n] 即为所求的不同走法的总数。