大厂面试算法（一）动态规划问题

小咪咪 2022-11-17 05:22 98阅读 0赞

# 动态规划问题 #

动态规划简单而言就是一种分治的思想，大事化小，小事化无的思想，即将大问题化为小问题，保存这些小问题的结果，方便后续处理大规模问题时直接使用这些结果

动态规划的特点：

1.  原问题分解为相似子问题
2.  所有子问题都只需要解决一次
3.  储存子问题的解

动态规划问题并非一个数学方程求解问题，而是需要找到状态与状态之间的递推关系

从以下四个角度考虑：

1.  状态的定义
2.  状态间的转移方程定义
3.  状态的初始化
4.  返回结果

适用场景：最大值/最小值 可不可行 是不是 方案个数

应用（1）斐波那契数列

*  递归求解

int Fibonacci(int n)
    {
    //递归
        if(n==0)
            return 0;
        if(n==1||n==2)
            return 1;
        return Fibonacci(n-1)+Fibonacci(n-2);
    }

*  DP求解

int Fibonacci(int n)
    {
        //状态 F[i]
        //初始化：F[0]=0,F[1]=1
        //状态转移方程：F[i]=F[i-1]+F[i-2]
        vector<int> F(n+1,0);
        F[1]=1;
        for(int i=2;i<=n;i++)
        {
            F[i]=F[i-1]+F[i-2];
        }
        return F[n];
    }

*  迭代求解

int Fibonacci(int n)
    {
        int f0=0;
        int f1=1;
        int fn;
        if(n<=1)
            return n;
        for(int i=2;i<=n;i++)
        {
            fn=f0+f1;
            f0=f1;
            f1=fn;
        }
        return fn;
    }

应用（2）青蛙跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级，，，也可以是n级台阶，求该青蛙跳上一个n级台阶总共有多少种跳法

推理：

f(1) :{1}//一级台阶  原地跳
    f(2) :{1,1} {2}//一级跳二级  以及原地跳
    f(3) :{1,2} {1,1,1}  {2,1}  {3}
    f(4) :{1,3} {1,1,2} {2,2} {1,2,1} {1,1,1,1} {2,1,1} {3,1} {4}
    
    状态转移方程：
    f(i):f(i-1)+f(i-2)+...f(0)//f（0）表示原地跳
    f(i-1):f(i-2)+f(i-3)+...f(0)
    则：
    f(i)=2*f(i-1)
    
    初始状态：
    f(1)=1;

通过上述分析，发现存在规律性，并且题目要求最终结果给出方法个数 根据枚举结果来看 呈现1 2 4 8.递增

class Solution {
    public:
        int jumpFloorII(int number) {
            if(number==0)
                return 0;
            int ret=1;
            for(int i=2;i<=number;i++)
            {
                ret*=2;
            }
            return ret;
        }
    };

应用（3）变形 矩形覆盖（此类题目本质上就是斐波那契数列的变形，但经过题目包装难以发现本质）

用2\*1的小矩形横着或竖着去覆盖更大的矩形，问：用n个2\*1的小矩形无重叠覆盖一个2\*n的大矩形，总共有多少种方法？

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70][]

状态转移方程：f(i-1)+f(i-2)

由图可知，有两种摆放方法，一种竖直放，一种横放，当i=1，即竖直放一种方式，当i=2，即2个横放一种方式

当i>3,即可f(i-1)+f(i-2)，两种方法组合

综上即为一个菲波那切数列问题

class Solution {
    public:
        int rectCover(int n) {
            if(n==0||n==1||n==2)
            {
                return n;
            }
            return rectCover(n-1)+rectCover(n-2);
        }
    };

应用（4）最大连续子序列和

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1][]

状态：以第i个元素结尾的最大连续子序列和

状态转移方程：

f(i)=max(f(i-1)+a\[i\],a\[i\])

初始状态：

f(0)=a\[0\]

返回值：max(f(i))

class Solution {
    public:
        int FindGreatestSumOfSubArray(vector<int> array) {
            if(array.size()==0)
            {
                return 0;
            }
            vector<int> maxsum(array);
            int res=maxsum[0];
            for(int i=1;i<array.size();i++)
            {
                maxsum[i]=max(maxsum[i-1]+array[i],array[i]);
                res=max(maxsum[i],res);
            }
            return res;
        }
    };

应用（5）给定一个字符串s和一组单词dict，判断s是否可以用空格分割成一个单词序列,使得单词序列中所有单词都是dict中的单词（序列可以包含一个或多个单词）

例如：s=\["leetcode"\]

dict=\["leet","code"\] 返回true 因为leetcod可以被分割为：“leet code”

状态f(i)：单词前i个字符是否可以成功分割

![20210512155137123.png][]

转移方程：j<i &&f(j)&&\[j+1,i\]是否可以在词典中找到

class Solution {
    public:
        bool wordBreak(string s, unordered_set<string> &dict) {
            int len=s.size();
            if(len==0)
                return false;
            vector<bool> dp(len+1,false);//默认为false
            for(int i=1;i<=len;i++)
            {
                if(dict.find(s.substr(0,i))!=dict.end())
                {
                    //[0.i]
                    dp[i]=true;
                    continue;
                }
                for(int j=i-1;j>0;j--)
                {
                    //j<i &&f(j)&&[j+1,i]
                    if(dp[j]&&dict.find(s.substr(j,i))!=dict.end())
                    {
                         dp[i]=true;
                         break;
                    }
                }
            }
            return dp[len];
        }
    };

应用（6）给出一个三角形，计算三角形顶部到底部的最小路径和，每一步都可以移动到下面一行相邻的数字

例如

【2】

【3，4】

【6，5，7】

最小的路径和：2+3+5=10

状态F（i,j）从0，0到最后一行的最小路径和

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70]: /images/20221022/c4613e2a992242e38c53c2667f2052f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MTMxNjEx_size_16_color_FFFFFF_t_70 1]: /images/20221022/b1cc7338f18940e58235d3776af22fcf.png
[20210512155137123.png]: /images/20221022/15dfc0555459424b85e728ad5e89da4d.png