动态规划1

53. 最大子序和

#define MAX(x,y) (((x) > (y)) ? (x) : (y))
int maxSubArray(int* nums, int numsSize){
    int *dp = (int *)malloc(sizeof(int) * (numsSize + 1)); // 添加dp[0] 为 0  表示初始状态
    memset(dp, 0, sizeof(int) * (numsSize + 1));
    int maxLen = INT_MIN; /* 要设置成最小值 */
    for (int i = 0; i < numsSize; i++) { // 遍历数组 更新 dp 数组
        dp[i + 1] = MAX(dp[i] + nums[i], nums[i]); // 当前数组 i 对应 dp 数组 i+1 (往后挪一格)
        maxLen = (dp[i + 1] > maxLen) ? dp[i + 1] : maxLen;
    }
    free(dp);
    return maxLen;
}

70, 爬楼梯

image.png

int climbStairs(int n)
{
    if (n == 1) {
        return 1;
    }
    if (n ==2) {
        return 2;
    }
    int *dp = (int *)malloc(sizeof(int) * n);
    dp[0] = 1;
    dp[1] = 2;
    for (int i = 2; i < n; i++) {
        dp[i] = dp[i-2] + dp[i-1];
    }
    return dp[n-1];
}