请教一道算法题（答题加米）

一共两种operations，分别是加一、乘4.
求从1到数字N的最小operation次数，并且乘4的操作不能超过X次.谢谢！

dp[j, 0] = j
dp[j, k] = min(dp[j - 1, k], 1 + dp[j / 4, k - 1])

改成/4和-1，从n变成1，那么能/4就/4，不能就-1减到能/4，/4用完了就一直减

联氢人 发表于 2019-10-3 05:22
准确来说是O(min(log(N), X))
因为如果X范围比较松的话，greedy倒推的下降速度是至多每四次操作N->N/4， ...

谢谢大神解答！方便帮我看一眼code写的对不对或者需要怎样优化吗？
class Solution {
    public int solution(int N, int x) {
     int ans = 0;
         while(N != 1){
                 if(N%4 == 0 && x >0 ){
                        N = N/4;
                        x--;
                        ans++;         
                 }
                 if(N%4 != 0 || x == 0){
                         N --;
                         ans++;
                 }           
         }
      return ans;
    }
  }

感觉是用动态规划？

仔细想想，
第一，你可以把n想成2进制或者4进制，这样加1还是加1，x4变成shift2或shift1.
第二，如果倒过来想，就是/4和-1如何最快降为1，这样能整除的情况下必然优先/4，不能就只能-1.

所以似乎就是不断//4和%4的过程？

不知道小帅 发表于 2019-9-25 07:09
感觉是用动态规划？

感觉动态转移方程不太容易想

QuantumDog 发表于 2019-9-25 08:53
仔细想想，
第一，你可以把n想成2进制或者4进制，这样加1还是加1，x4变成shift2或shift1.
第二，如果倒过 ...

这个想法挺有意思的，你方便po一下pseudo-code吗

这个题应该不是用DP的吧，速度差的有点多
Greedy比较好，尽量把乘4往后放。这个跟Knapsack problem 还不一样，两个操作是乘4和加一，所以greedy一定可以找到最优解

感觉是greedy吧
倒推，当N%4!=0的时候必然是-1，当N%4==0的时候如果乘法次数还没到上线，反证法可得此处/4（相当于正向的*4）必然比做四次（或者4*a次，anyway）-1 要省总次数dp也不是不可以做，但是复杂度就是O(Nk)时间O(Nk)空间，同时greedy的话就是O(logN), 高下立判...

直接贪心就可以吧。。。目标不被4整除在-1，很容易证明的