动态规划之实际问题

algorithm

两个操作的键盘

• 两个操作的键盘
• 题目大意：键盘只有两种操作，一种是拷贝(copy)，一种之粘贴(paste)。初始情况在纸上有个字符$A$，每次只能拷贝纸上的数据，不能局部拷贝，拷贝后存在粘贴板里，每次粘贴都从粘贴板里复制到纸上。目标是给定一个$n$，求最少需要多少次上述的拷贝粘贴操作能够生成$n$个A。
• 例如：打印三个A，初始情况，一个A，执行一次拷贝，一次粘贴，在一次粘贴，就可以生成三个A，所需要的次数为3。

思路1

• 可以把这个问题形式化为C表示拷贝(copy),P表示(paste)，那么n可以认为是$[cpp]...[cppp...]$
• 假设$dp[i]$ 表示生成$i$个A需要的步数，那么这个步数可能由前一步的那些A的个数通过拷贝复制操作得来呢？
• 这么来考虑，如果已知$dp[i]$的操作，那么我们可以得到$dp[2*i]$，需要的就是在$dp[i]$情况下，一次拷贝，一次复制。也就是$dp[2*i] = dp[i] + 2$，同理$dp[3*i] = dp[i] + 3$，$dp[k*i] = dp[i] + k$，这下我们明白，在$i$个A的情况，可能是由前面的$i$的某个因子$j,i\%j == 0$，通过1次复制，$i/j$次粘贴得到的。所以有如下的递推公式
  $$dp[i] = \underset{1\le j \le i/2 \&\& i\%j=0}{min}\{dp[j] + i / j\}$$

int minSteps(int n) {
        vector<int> dp( n + 1 , 0);
        for(int i = 2; i<= n; i++ ) {
            dp[i] = i;
            int m = i / 2;
            for(int j = 1; j <= m; j++ ) {
                if(i % j == 0 ) {
                    int c = i / j - 1;
                    c += 1;
                    dp[i] = min(dp[i],dp[j] +c );
                }
            }
        } 
        return dp[n];
    }

• 时间复杂度：$O(n^2)$，空间复杂度：$O(n)$
  

broken-calculator

• broken-calculator
• 题目大意：这个计算机只能执行两种操作，对于计算器上展示的数字，X，能够执行double操作，是的计算器展示2*X,或者执行减1操作，计算器展示X-1

int brokenCalc(int X, int Y) {
        if( X  == Y )
            return 0;
        if( X > Y )
            return X - Y;
        if(Y  & 0x01 ) {
            return brokenCalc(X, Y + 1 ) + 1 ;
        }else {
            return brokenCalc(X, Y / 2 ) + 1;
        }
        return 0;
 }

• 时间复杂度：$O(n)$，空间复杂度：$O(n)$

构成三角形的个数

题目大意

• 三角形的个数
• 给定一个非负数组，确定这个数组中的三个数，能够成三角形的个数
• 例如：[2,2,3,4]，可以构成三角形的个数为3，$(2,3,4),(2,3,4),(2,2,3)$

分析

• 构成三角形的充分条件是，任何两边的和大约第三边

思路1

• 暴力搜索
• 枚举所有的$(i,j,k)$ 判断是否满足构成三角形的充分条件

int triangleNumber(vector<int>& nums) {
        int count = 0;
        for (int i = 0; i < nums.length - 2; i++) {
            for (int j = i + 1; j < nums.length - 1; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    if (sum2judge(nums,i,j,k)  && sum2judge(nums,i,k,j) && sum2judge(nums,j,k,i))
                        count++;
                }
            }
        } I
        return count;
}
int sum2judge(vector<int>& nums, int i,int j,int k) {
    return nums[i]  + nums[j] > nums[k];
}

• 时间复杂度:$O(n^3)$,空间复杂度:$O(1)$

思路2

• 查找的是满足构成三角形的三个边，我们可以通过查找来解决这个问题。
• 假设我们知道两条表$a,b$，那么第三条边满足的条件就是$a + b > c$ ，我们可以先对数组排序，对于任意的两条边$nums[i],nums[j],i \lt j$ 查找$k,nums[i] + nums[j] > nums[k],k \gt j \gt i$。查找$k$，对于有序数组可以使用二分查找。

int triangleNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int n = nums.size();
        int sum = 0;
        for( int i =  0 ;i < n; i++ ) {
            for( int j = i + 1;j < n; j++ ) {
                int u = nums[i] + nums[j] - 1;
                auto hi = upper_bound(nums.begin() + j + 1, nums.end(), u);
                int c = hi - (nums.begin() + j + 1);
                if ( c > 0 ) {
                    sum += c;
                }
            }
        }
        return sum;
}

• 时间复杂度:$n^2log(n)$，空间复杂度:$log(n)$，排序所需栈空间。

思路3

• 优化查找k的过程