求优化dp

学术版

穼柗° @ 2024-11-28 21:38:21

x=y$ 时，$dp_{x,y}=1\\ x>y$ 时，$dp_{x,y}=dp_{x-2,y}+dp_{x-1,y-1}

怎么样把它优化到 O(1) 或 O(\log{x})？

by W_SUN @ 2024-11-28 21:53:19

@穼柗°

    for(int i=2;i<=10;i++){
        for(int j=1;j<=i;j++){
            if(i==j){
                dp[i][j]=1;
            }
            else{
                dp[i][j]=dp[i-2][j]+dp[i-1][j-1];   
            }
            cout<<dp[i][j]<<" ";
        }
        cout<<endl;
    }

使用这段代码输出后可以观察到对于 dp 的值从每一行最后一个向左下方斜着看构成杨辉三角

by 穼柗° @ 2024-11-28 22:08:17

@W_SUN 但是我的 \text{dp} 方程还有一句：x=y+1时，dp_{x,y}=2

by W_SUN @ 2024-11-28 22:38:37

@穼柗° 你限定y小于等于x这种情况不可能啊

上一页 |