题目

给你一个非负整数 num ，请你返回将它变成 0 所需要的步数。如果当前数字是偶数，你需要把它除以 2 ；否则，减去 1 。

示例 1：

输入：num = 14
输出：6

解释：
步骤 1) 14 是偶数，除以 2 得到 7 。
步骤 2） 7 是奇数，减 1 得到 6 。
步骤 3） 6 是偶数，除以 2 得到 3 。
步骤 4） 3 是奇数，减 1 得到 2 。
步骤 5） 2 是偶数，除以 2 得到 1 。
步骤 6） 1 是奇数，减 1 得到 0 。

示例 2：

输入：num = 8
输出：4

解释：
步骤 1） 8 是偶数，除以 2 得到 4 。
步骤 2） 4 是偶数，除以 2 得到 2 。
步骤 3） 2 是偶数，除以 2 得到 1 。
步骤 4） 1 是奇数，减 1 得到 0 。

示例 3：

输入：num = 123
输出：12

链接

1342. 将数字变成 0 的操作次数

代码

模拟

class Solution {
public:
    int numberOfSteps(int num) {
        int ans = 0;
        while ( num != 0) {
            if(num % 2) num--;
            else num /= 2;
            ans++;
        }
        return ans;
    }
};

动态规划

确定状态

dp[i] 表示把 i 变成零所需要的操作次数
确定状态转移方程

若 i 为偶数：

dp[i] = dp[i / 2] + 1

若 i 为奇数：

dp[i] = dp[i - 1] + 1
确定初始状态

dp[0] = 0
确定计算顺序

递推类问题都是从前向后

class Solution {
public:
    int numberOfSteps(int num) {
        int dp[num + 1];
        dp[0] = 0;
        for(int i = 1 ; i <= num ; ++i) {
            if(i % 2) dp[i] = dp[i - 1] + 1;
            else dp[i] = dp[i / 2] + 1;
        }
        return dp[num];
    }
};