【C语言】初识动态规划和运用

题目描述

题目来源： 除自身以外数组的乘积 - 力扣（Leetcode）

给你一个整数数组nums，返回数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在32 位整数范围内。

请**不要使用除法，**且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]
1
2

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]
1
2

提示：

• 2 <= nums.length <=
• -30 <= nums[i] <= 30
• 保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在32 位整数范围内

思路解析

暴力法

既然是算除自己以外所有的数的乘积，那么在不能用除法的情况下最容易想到的就是，把自己变成1，然后后面算完再变回来。

这个思路很简单我们直接上代码

int* productExceptSelf(int* nums, int numsSize, int* returnSize){
    int* arr = malloc(4*numsSize);
    *returnSize = numsSize;
    //有n个数据就循环n次
    for (int i = 0; i < numsSize; i++){
        //先把当前的数据存下来然后变为1
        int tmp = nums[i];
        nums[i] = 1;
        int product = 1;
        //算乘积
        for (int j = 0; j < numsSize;j ++){
            product *= nums[j];
        }
        //存值并且把当前数据变回去
        arr[i] = product;
        nums[i] = tmp;
    }
    return arr; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

这个暴力解法，在数据量小的时候还是可以用的，但是一旦数据量大了，计算量就会飙升

那么上面这个代码也很明显，因为这个原因是无法通过提交的

动态规划

动态规划介绍

由于这是第一次介绍动态规划思想，所以我们先简单的介绍一下这个思想，如果只想想看解题思路可以直接看后面的动态规划解题部分

动态规划的思想是将问题分解为一系列子问题，然后将每个子问题的解存储起来，以便以后需要时能够快速的访问和使用。通过这种方式，动态规划可以在不重复计算子问题的情况下，更有效地求解原问题。

那么是什么意思呢？

举一个超级简单的例子，我们怎么只用1和加法算2和3。

那要是最直接的算：算3就是1+1+1，2又等于1+1，那么就要用三次加号。

但假如我们用动态规划的思想，我们就先将基础情况设为1，然后下一个情况是2 = 1 + 1，这个时候我们就直接把2存起来。那么我们算3的时候就不用去1+1+1而是用2+1，那么总共就用了两次加号。

上面这个例子可能看不出来什么优化，你可能就想：这不就少了一次运算吗？有啥用？

但是注意，我这里举的例子是为了方便理解，例子是一个数据量极低，并且计算极为简单的，一旦数据量变大，优化就会变得及其明显了。

实际上，这个思想和我们之前学过的递归思想很像，都是大问题化小问题。

但是动态规划的优势是，从底层往上走，当上面的数据用到下面的数据的时候可以直接调用而不用运算。

而递归则是从高层往下走，不断分支，每一个小分支都要重新计算，计算量非常巨大。

---

一般动态规划大概分为三个步骤：

1. 定义状态：确定原问题和子问题中变化的量，以及变化量的取值范围

2. 状态转移：确定如何从子问题的解推导出原问题的解。这通常需要根据问题的特点设计转移方程

3. 边界条件：确定初始状态的值，以及问题的边界范围

接下来我们以一个简单的求解斐波那契数列的来帮我们了解一下三个步骤

#define N 10
//定义状态,变化量最大值是n
int fib(int n) {
	if (n == 0 || n == 1) {
		return n;
	}
	//由于VS不支持变长数组，这里先用宏代替
	//正常使用用变量即可
	//为什么用dp命名，是因为动态规划的名字是Dynamic Programming，就是首字母简写
	int dp[N + 1];
	
	
	//定义边界条件
	dp[0] = 0;
	dp[1] = 1;

	//状态转移，最关键的一步，要想出怎么将问题拆分。这里就比较简单,是前两个数相加
	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	return dp[n];
}
int main() {
	printf("%d", fib(10));
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

实际上，最关键的两个步骤就是定义边界和状态转移，其中难度最高的是状态转移，因为它变化性极强，需要根据实际情况来进行判断

再看一个动态规划求阶乘的代码

#define N 10
int fact(int n) {
	if (n == 1 || n == 0) {
		return 1;
	}
	//依旧借用一下宏
	int dp[N+1];
	dp[0] = 1;
	dp[1] = 1;
	//第n个阶乘等于n乘以第n-1个阶乘
	for (int i = 2; i <= n; i++) {
		dp[i] = i * dp[i - 1];
	}
	return dp[n];
}
int main() {
	printf("%d", fact(10));
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

动态规划解题

上面简单的了解了一下我们的动态规划思想，那么我们在这一题中该如何运用呢？

首先我们观察一下这个题目，他说的是除自身外所有数的乘积，也就是左边所有数的乘积乘以右边所有数的乘积

那么这个分别求左边和右边的乘积，是不是和我们上面举例子的求阶乘代码很像，都是可以用前面的乘积来帮忙求解的，那么我们就以这个入手，先写一段求左边乘积的代码

	int* dpL = (int*)malloc(sizeof(int) * numsSize);
	//定义边界条件,第一个数左边没有数字所以先定义为1
	dpL[0] = 1;
    dpL[1] = nums[0];
        for (int i = 2; i < numsSize; i++) {
            //第i个数的左边数乘积，等于i-1个数字的左边数乘积*第i-1个数字
            dpL[i] = dpL[i - 1] * nums[i - 1];
        }
1
2
3
4
5
6
7
8

然后就是算右边的乘积，实际上就是反向来一波，没什么难度

    int* dpR = (int*)malloc(sizeof(int) * numsSize);
    dpR[numsSize-1] = 1;
    dpR[numsSize-2] = nums[numsSize-1];
    for (int i = numsSize - 3; i >=0 ; i--){
        dpR[i] = dpR[i + 1] * nums[i + 1];
    }
1
2
3
4
5
6

那么最后把它们乘起来就好了

    int* arr = (int*)malloc(sizeof(int) * numsSize);
    for(int i = 0; i < numsSize; i++){
        arr[i] = dpL[i]*dpR[i];
    }
1
2
3
4

那么就可以正常提交了

内存优化

上面的代码虽然已经解决了时间的问题，可是也可以明显看出，我们的代码开辟了三块空间，非常耗内存，那么有没有什么地方可以优化呢？

实际上，反正我们最后都是要将左边的乘积和右边的乘积乘到一起，那么为什么我们不直接在求右边的乘积的时候直接让它乘以左边的乘积呢？这样就可以只开辟一块空间并完成所有任务了

后半的代码修改如下

    //最右边的数字右边没有数字，不用乘任何数
    //由于是直接乘进去，这里要开一个数字来存第i个数右边的乘积
    int tmp = nums[numsSize-1];
    for (int i = numsSize - 2; i >=0 ; i--){
        //直接用自身乘以右边的数乘积
        dp[i] *= tmp;
        //改变右边的数乘积方便下一次运算
        tmp *= nums[i];
    }
1
2
3
4
5
6
7
8
9

那么这个代码的空间占用就比刚刚那个代码小很多了

代码预览

暴力法的代码上面直接放了这里就不放了

动态规划解法代码

int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
    int* dp = (int*)malloc(sizeof(int) * numsSize);
    dp[0] = 1;
    dp[1] = nums[0];
    for (int i = 2; i < numsSize; i++) {
        dp[i] = dp[i - 1] * nums[i - 1];
    }
    int tmp = nums[numsSize - 1];
    for (int i = numsSize - 2; i >= 0; i--) {
        dp[i] *= tmp;
        tmp *= nums[i];
    }
    *returnSize = numsSize;
    return dp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15