shijilin1


私信TA

用户名:Fl1ui

访问量:3258

签 名:

等  级
排  名 364
经  验 3742
参赛次数 0
文章发表 5
年  龄 99
在职情况 学生
学  校 望子成龙小学
专  业

  自我简介:

解题思路:

由前无效性原则入手:每个元素只跟上一层的有关
所以可以用滚动数组优化,减少空间复杂度

但是要注意的是,例如num[i][j]=num[i-1][j-1]+num[i-1][j]

微信图片_20210601161941.png

所以在推算新的一层数据的时候要采用从后往前推的办法

1.png


1.png

... ...

1.png


参考代码:

#include<iostream>
using namespace std;
 
long long num[1000001] = {0, 1}; // 滚动数组,0位不存更方便,1000*1000=1000000
 
int main () {
    int i, j;
    cin >> i >> j;
    for(int a = 1; a <= i; a ++) { // 后推
        for(int b = a; b > 0; b --) {
            num[b] += num[b-1];
        }
        // 展示过程:
//      for(int b = 1; b <= a; b ++) {
//          cout << num[b] << " ";
//      }
//      cout << endl;
    }
    cout << num[j];
    return 0;
}


 

0.0分

3 人评分

  评论区