这个算法题的3、4、5有没有会做的啊

Question

就写345问就行，有没有会写的啊，关于动态规划的.（这个提问要求30字实在没什么好写的、冲字数）

Answer 1

i从1到n遍历，求出每个r[i]。求r[i]的方法是j从1到i-1遍历，求出最大的r[i-j]+r[j]，再将最大的r[i-j]+r[j]与p[i]比较，较大的一个就是r[i]，若p[i]较大，则将s[i]赋值i，否则赋值j。输出最优解就是输出s[i]，再把i赋值为i-s[i]，两个过程循环，直到i与s[i]相等。

外层循环次数为n，内层循环次数为1+2+3+……+n-1，总体时间复杂度为O(n*n)

c代码：

#include<stdio.h>
int main() {
    int p[11] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30}, r[11], s[11], n = 10;
    int i, j;

    //求r[i]和s[i]
    i = 1;
    while (i <= n) {
        r[i] = p[i];
        j = 1;
        s[i] = i;
        while (j < i) {
            if (r[j] + r[i - j] >r[i]) {
                r[i] = r[j] + r[i - j];
                s[i] = j;
            }
            j++;
        }
        i++;
    }

    //输出最优解
    printf("请输入长度: ");
    scanf("%d", &i);
    while (i != s[i]) {
        printf("%d ", s[i]);
        i = i-s[i];
    }
    printf("%d",s[i]);
    return 0;
}

执行结果（为了方便显示，我临时套了个死循环）：