整数累加求1-r的和

本文将介绍整数累加求1-r的和问题的解决方法，使用不同的算法，从多个角度解释。这是一个基础问题，本文主要介绍常见的几种方法来解决它。

一、暴力解法

暴力解法就是直接使用循环累加1到r的所有整数，计算它们的和。代码如下：

//C++代码
int sum(int r){
    int ans=0;
    for(int i=1;i<=r;i++){
        ans+=i;
    }
    return ans;
}

这种方法的时间复杂度是O(r)，时间效率不够高。

二、高斯求和法

高斯求和法是一种通过找规律来计算1到n之间所有整数的和的方法。相信大家都学过高斯数列的求和公式：S(n) = n * (n+1) / 2。

同理，对于1到r之间的整数求和，我们可以使用类似的公式：S(r) = r * (r+1) / 2。

代码如下：

//C++代码
int sum(int r){
    return r*(r+1)/2;
}

使用高斯求和法，时间复杂度是O(1)，时间效率非常高。

三、递归解法

递归是一种解决问题的方法，它把一个大问题分解成若干个小问题解决。对于整数累加求1-r的和，我们可以分解为1加上2到r的和，即S(r) = 1 + S(r-1)。递归代码如下：

//C++代码
int sum(int r){
    if(r==1){
        return 1;
    }
    return r+sum(r-1);
}

递归解法在时间复杂度上和暴力解法一样，都是O(r)，但是在代码实现上更加简洁和优雅。

四、迭代解法

迭代也是一种解决问题的方法，和递归的思路相反，它把一个小问题逐渐扩大，解决整个大问题。对于整数累加求1-r的和，我们可以使用迭代来实现。代码如下：

//C++代码
int sum(int r){
    int ans=0;
    for(int i=1;i<=r;i++){
        ans+=i;
    }
    return ans;
}

迭代解法和暴力解法非常类似，只是没有使用递归。时间复杂度也是O(r)。

五、动态规划解法

动态规划是一种自底向上的解决问题的方法。对于整数累加求1-r的和，我们可以使用一个数组来存储1到r之间所有整数的和，然后通过递推公式来计算。代码如下：

//C++代码
int sum(int r){
    vector ans(r+1,0); //初始化数组
    ans[1]=1;
    for(int i=2;i<=r;i++){
        ans[i]=ans[i-1]+i;
    }
    return ans[r];
}

动态规划解法可以在一定程度上优化时间复杂度，但是需要额外的空间。