算法自学

参考资料:

https://www.zhihu.com/question/39948290https://blog.csdn.net/zw6161080123/article/details/80639932 算法引入

我们先考虑一个经典问题:
小明要爬上一个n级的台阶, 他每次可以走1级或2级, 求不同的走法数.

代码:

int solve(int n) {
	if (n == 1)return 1;
	else if (n == 2)return 2;
	else return solve(n - 1) + solve(n - 2);
}
int main() {
	int n;
	cin >> n;
	cout << solve(n);
	return 0;
}

时间复杂度: O(2^n)
我们可以发现, 上述算法包含着大量的重复计算:
假设n=5, 根据上述算法, 我们需要先计算solve(4)和solve(3)
而要计算solve(4), 必须先计算solve(3)和solve(2)
我们注意到solve(3)被计算了两次.
当问题规模更大时, 重复计算会更多, 导致问题不能在理想的时间内得到解决.

如果我们将已经解决的问题的结果保存下来, 在解决新问题时直接调取旧问题的结果, 就能节省不少时间, 这就是最简单的动态规划

#include
#include
using namespace std;
int dp[100];
void solve(int n) {
	if (n <= 2) return;
	else {
		for (int i = 3; i <= n; i++) {
			dp[i] = dp[i - 1] + dp[i - 2];
		}
	}
}
int main() {
	dp[1] = 1, dp[2] = 2;
	int n;
	cin >> n;
	solve(n);
	cout << dp[n];
	return 0;
}

时间复杂度: O(n)

最优化原理: 问题的最优解所包含的子问题的解也是最优的.无后效性: 某个阶段的决策一旦确定, 就不受后续决策的影响.有重叠的子问题(该性质不是必须的, 但是若没有这条性质, 动态规划算法将不具有优势). 算法实现的步骤

创建一个数组(数组的维数与问题相关), 用以保存子问题的结果.设置数组的边界值.求出状态转移方程, 即找到每个状态与上一个状态的关系.返回需要的值.

对应题目: LeetCode第300题

代码实现:

int lengthOfLIS(int* nums, int numsSize){
    int dp[2505];
    for(int i=0;inums[j]){
                dp[i]=fmax(dp[i],dp[j]+1);		//状态转移方程
            }
        }
    }
    int max=0;
    for(int i=0;imax) max=dp[i];
    }
    return max;
}
// 时间复杂度O(n^2)

算法改进:
定义tail数组, tail[i]表示: 长度为i+1的所有递增子列的最小尾元素.
我们容易直到, tail数组是严格单调递增的.
状态转移定义为:

若当前元素e大于tail[i], 则tail[i+1]=e(得到了一个长度为i+2的递增子列, 最小尾元素为e)若当前元素e小于等于tail[i], 二分查找到tail数组中第一个大于e的数字, 并将其更新为e

当我们遍历整个数组后, tail数组中的元素个数即为最长递增子列的长度.

代码实现:

class Solution {
public:
    int lengthOfLIS(vector& nums) {
        int tail[2505];
        tail[0]=nums[0];
        int ans=1;
        int len=nums.size();
        for(int i=1;itail[ans-1]){
                tail[ans++]=nums[i];
            }
            else if(nums[i]==tail[ans-1]) continue;
            else{
                int L=0,R=ans-1,flag=0;
                while(L<=R){
                    int mid=(L+R)>>1;
                    if(nums[i]>tail[mid]) L=mid+1;
                    else{
                        flag=mid;
                        R=mid-1;
                    }
                }
                if(nums[i]==tail[flag]) continue;
                tail[flag]=nums[i];
            }
        }
        return ans;
    }
};
//时间复杂度O(nlogn)

对应题目: LeetCode第53题

代码实现:

class Solution {
public:
    int maxSubArray(vector& nums) {
        int len=nums.size();
        int dp[100005];
        dp[0]=nums[0];
        int max=dp[0];
        for(int i=1;imax) max=dp[i];
        }
        return max;
    }
};